Codeforces Round #451 (Div. 2) A B C D E
Codeforces Round #451 (Div. 2)
A Rounding
题目链接：
http://codeforces.com/contest/898/problem/A
思路：
小于等于5向下，大于补上差值输出
代码：
#include
using namespace std;
typedef long long ll;
int main() {
ll n;
scanf("%I64d",&n);
int r=n%10;
if(r<=5) printf("%I64d\n",n-r);
else printf("%I64d\n",n+10-r);
return 0;
}
B Proper Nutrition
题目链接：
http://codeforces.com/contest/898/problem/B
思路：
暴力枚举
代码：
#include
using namespace std;
typedef long long ll;
int main() {
ll a,b,n;
scanf("%I64d",&n);
scanf("%I64d %I64d",&a,&b);
bool flag=false;
ll index=n/a;
for(ll i=0;i<=index;++i) {
ll temp=n-i*a;
if(temp/b*b==temp) {
printf("YES\n");
printf("%I64d %I64d\n",i,temp/b);
flag=true;
break;
}
}
if(!flag) printf("NO\n");
return 0;
}
C Phone Numbers
题目链接：
http://codeforces.com/contest/898/problem/C
思路：
暴力大法。
就是string排序的时候重写一下cmp，另外sort之后不要unique，不然会wa5
代码：
#include
using namespace std;
vector vec[21];
map mp;
set se;
bool cmp(string a, string b) {
if(a.length()!=b.length()) return a.length()>n;
string name;
int tot;
string number;
cnt=1;
for(int i=0;i>name;
cin>>tot;
if(se.count(name)==0) {
mp[cnt]=name;
se.insert(name);
++cnt;
}
for(auto it=mp.begin();it!=mp.end();it++) {
if(it->second==name) {
id=it->first;
break;
}
}
for(int j=0;j>number;
vec[id].push_back(number);
}
}
cout<0) cout<<" "< D Alarm Clock
题目链接：
http://codeforces.com/contest/898/problem/D
题目大意：
不允许在m分钟内有k个闹钟响，每个闹钟响一分钟，求最少关掉的闹钟数目
思路：
首先其实按照从小到大的时间顺序查看，因为这相当于一个m大的滑块在整个数组上划一遍，所以使用队列就可以，其实就是贪心的思想。
代码：
#include
using namespace std;
const int maxn = 1000005;
int a[maxn];
int main() {
int n,m,k,num,res=0,tot=0;
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;++i) a[i]=0;
for(int i=1;i<=n;++i) scanf("%d",&num),a[num]=1;
for(int i=1;i<=1e6;++i) {
if(a[i]) ++tot;
if(i>m&&a[i-m]) --tot;
if(tot==k) {
--tot;
++res;
a[i]=0;
}
}
printf("%d\n",res);
return 0;
}
E Squares and not squares
题目链接：
http://codeforces.com/contest/898/problem/E
思路：
统计出给定序列的完全平方数和非完全平方数，看看是要补平方数还是补非完全平方数。记录下每个数距离最近的完全平方数的插值，同时记录下改为非完全平方数的最小差值。根据是前面所述的两种情况中的一种进行排序，选择出最小的数据插值求和即可。
代码：
#include
using namespace std;
typedef long long ll;
const int maxn = 200005;
struct node {ll num,a,b;int d;}ans[maxn];
bool cmp1(node x, node y) {return x.a1) ans[i].b=1;
else ans[i].b=2;
}
d2=n-d1;
if(d2>d1) {
cnt=n/2-d1;
sort(ans,ans+n,cmp1);
for(int i=0;id2) {
cnt=n/2-d2;
sort(ans,ans+n,cmp2);
for(int i=0;i