Make It Equal
There is a toy building consisting of hi.
Let's define operation slice on some height
Let's name slice as good one if its cost is lower or equal to k≥n).
Calculate the minimum number of good slices you have to do to make all towers have the same height. Of course, it is always possible to make it so.
The first line contains two integers n≤k≤109) — the number of towers and the restriction on slices, respectively.
The second line contains 1≤hi≤2⋅105) — the initial heights of towers.
Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.
5 5
3 1 2 2 4
2
4 5
2 3 4 5
2
In the first example it's optimal to make 4).
cf的一道特烦的题，超时到爆，然后发现可以用前缀和。
首先把所有塔的高度减去其中的最小值，问题就变成了将塔消完所需要的步数。（可以不减，那样最后就是>min而不是>0）
用前缀和做一个数组brr，即这么高的塔有几个；
然后从最大的判断相减就好了，（注意前一个高度等于原来的加后一个）（相加和都不超过给定的k）
#include<iostream>
#include<algorithm>
using namespace std;
int brr[200001]={0};
int main()
{
int n,m;
cin>>n>>m;
int arr[200001];
int min=200001,max=0;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
if(arr[i]<min)
min=arr[i];
if(arr[i]>max)
max=arr[i];
}
for(int i=1;i<=n;i++)
{
brr[arr[i]-min]++;
}
int k=0,sum=0;
for(int i=max-min;i>0;i--)
{
k+=brr[i];
brr[i-1]+=brr[i];
if(k>m)
{
brr[i-1]-=brr[i];
i++;
k=0;
sum++;
}
}
if(k>0)
sum++;
cout<<sum;
}