F - Make It Equal CodeForces - 1065C

题目大意:有n座塔,塔高h[i],每次给定高度H对他们进行削切,要求每次削掉的所有格子数不能超过k个,输出最少削几次才能使所有塔的高度相同。

思路一:差分+贪心

对于每一个高度h,用一个数组让1~h的数,每一个都加一。用差分求一下后缀和可以完成。

AC code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2E5+7;
ll arr[N];
int main()
{
    ll n,k;
    cin>>n>>k;
    ll x;
    ll c=0;
    for(ll i=1;i<=n;i++){
        cin>>x;
        c=max(x,c);
        arr[x]++;
    }
    for(ll i=c;i>=1;i--){
        arr[i]+=arr[i+1];
    }
    ll sum=0;
    ll cnt=0;
    for(ll i=c;i>=1;i--){
        if(arr[i]==n){
            if(cnt!=0){
                sum++;
                break;
            }
            else break;
        }
        cnt+=arr[i];
        if(cnt>k){
            cnt=arr[i];
            sum++;
        }
    }
    cout<<sum<<endl;
    return 0;
}

用线段树加二分也可以过:https://blog.csdn.net/Amovement/article/details/83449446

上一篇:【题解 CF1205A Almost Equal】


下一篇:Java实现对象equal()函数的方法