C. Make It Equal

时间:2021-01-14 22:20:34

链接

[http://codeforces.com/contest/1065/problem/C]

题意

给你n个高度hi的塔,让你把高的部分切掉,使得最后所有塔一样高,而且每次切的高度之和不大于k

分析

从最高的塔,贪心地切到最低的塔,判断不大于k,即可

具体看代码

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll h[200010];
int cnt[200010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("in.txt","r",stdin);
ll n,k,i;
memset(cnt,0,sizeof(cnt));
cin>>n>>k;
ll x=1000000010;
ll d=0;
for(i=1;i<=n;i++)
{
cin>>h[i];
cnt[h[i]]++;
x=min(h[i],x);
d=max(d,h[i]);
}
ll sum=0,ans=0;
for(i=d;i>x;i--){
cnt[i]+=cnt[i+1];
if(sum+cnt[i]>k){
ans++;
sum=cnt[i];
}
else {
sum+=cnt[i];
}
}
cout<<ans+(sum>0?1:0)<<endl;
return 0;
}