Codeforces 1065C Make It Equal(差分+贪心)

题意：n个塔，第i个塔由$h_i$个cube组成，每次可以切去某高度h以上的最多k个cube，问你最少切多少次，可以让所有塔高度相等

k>=n, n<=2e5

思路：差分统计每个高度i有的方块数nh[i]，然后从高到低贪心的切就行了

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

//#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x))

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = ;

const int maxn = 2e5+;

const int maxm = 2e5+;

const ll inf = 0x3f3f3f3f3f3f3f3f;

const db pi = acos(-1.0);

int nh[maxn];

int main() {

    int n;ll m;

    scanf("%d %lld", &n, &m);

    int vol = ;

    for(int i = ; i <= n; i++){

        int c;

        scanf("%d", &c);

        nh[]++;nh[c+]--;

    }

    for(int i = ; i <= maxn; i++){

        nh[i]+=nh[i-];

    }

    int tmp = ;

    int ans = ;

    for(int i = maxn; i >= ; i--){

        if(nh[i]==n)break;

        if(tmp+nh[i]>m){

            tmp=nh[i];

            ans++;

        }

        else tmp+=nh[i];

    }

    if(tmp>)ans++;

    printf("%d", ans);

    return ;

}