题目大意:有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