Educational Codeforces Round 52 (Rated for Div. 2)

A. Vasya and Chocolate

解题思路：简单水过！

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 int t;LL s,a,b,c,ans;
 5 int main(){
 6     while(cin>>t){
 7         while(t--){
 8             cin>>s>>a>>b>>c;
 9             LL tp=s/c;
10             LL tp1=tp/a;
11             LL tp2=tp1*(a+b);
12             cout<<tp2+(s-tp1*a*c)/c<<endl;///不足a个，则剩下的钱单独买x个价格为c即可。
13         }
14     }
15     return 0;
16 }

B. Vasya and Isolated Vertices

解题思路：分别计算最小孤立点和最大孤立点的个数，不难，详解看代码。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL maxn=1e5+5;
 5 LL n,m,tp,aw,num[maxn]={0};
 6 int main(){
 7     for(LL i=1;i<maxn;++i)num[i]=i*(i-1)/2;///计算i个节点的完全图的总边数
 8     while(cin>>n>>m){
 9         aw=n-(lower_bound(num,num+n+1,m)-num);///要从num起始数组开始查找，当m为0时，占用的节点数目为0，即下标为0
10         if(n%2==0){///n为偶数
11             if(m>=n/2)tp=0;///如果m不小于n的一半，则没有孤立点
12             else tp=(n/2-m)*2;///否则为n/2-m条边对应的2倍节点数目
13         }else {
14             if(m>=n/2+1)tp=0;///如果m不小于n/2+1，则没有孤立点
15             else tp=n-m*2;///否则为剩下最少的节点数目为n-2m
16         }
17         cout<<tp<<' '<<aw<<endl;
18     }
19     return 0;
20 }

C. Make It Equal

解题思路：将高度升序排，然后从高到低，从上到下模拟切，每一刀要求最多只能切出k个小正方形。

AC代码：

 1 #include<iostream>
 2 #include <map>
 3 using namespace std;
 4 typedef long long LL;
 5 map<int, int> mp; int cnt, ans, x, n, k, siz;
 6 int main(){
 7     while (cin >> n >> k){
 8         mp.clear(); ans = 0;
 9         while (n--){ cin >> x; mp[x]++; }
10         while ((siz = mp.size()) > 1){
11             cnt = 0;
12             for (auto it = mp.rbegin(); it != mp.rend() && cnt + (it->second) <= k && (siz = mp.size()) > 1;){
13                 cnt += it->second;//加上次数
14                 mp[it->first - 1] += it->second;//前一个矩形添加一个小正方形，即高度加1，将后面切得的正方形个数累加到前面
15                 mp.erase(it->first);//删除当前的高度
16             }
17             ans++;
18         }
19         cout << ans << endl;
20     }
21     return 0;
22 }