cf Educational Codeforces Round 52 C. Make It Equal

本文主要是介绍cf Educational Codeforces Round 52 C. Make It Equal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
C. Make It Equal
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There is a toy building consisting of n towers. Each tower consists of several cubes standing on each other. The i-th tower consists of hicubes, so it has height hi.Let’s define operation slice on some height H as following: for each tower i, if its height is greater than H, then remove some top cubes to make tower’s height equal to H. Cost of one “slice” equals to the total number of removed cubes from all towers.

Let’s name slice as good one if its cost is lower or equal to k (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.

Input
The first line contains two integers n and k (1≤n≤2⋅10^5, n≤k≤10 ^9) — the number of towers and the restriction on slices, respectively.
The second line contains n space separated integers h1,h2,…,hn (1≤hi≤2⋅10^5) — the initial heights of towers.

Output
Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.

Examples
input
5 5
3 1 2 2 4
output
2
input
4 5
2 3 4 5
output
2
Note
In the first example it’s optimal to make 2 slices. The first slice is on height 2 (its cost is 3), and the second one is on height
1 (its cost is 4).

中文：
给你一堆由正方形叠成的长条，每个长条的高度是hi，表示有hi个正方形叠成，现在给你一个操作，这个操作是选定一个高度，可以去掉这个高度以上的所有方形，但是这些方形的数量不能超过k，问你最少操作多少次，能使得所有长条高度相同。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,k;
ll h[200001];
ll sum[200001];
int main()
{ios::sync_with_stdio(false);while(cin>>n>>k){memset(sum,0,sizeof(sum));for(int i=0;i<n;i++)cin>>h[i];sort(h,h+n);ll Max=h[n-1];for(int i=1;i<=Max;i++){sum[i]=n-(ll)(lower_bound(h,h+n,i)-h);}if(sum[Max]==n){cout<<0<<endl;continue;}ll Min=1;for(ll i=Max;i>=1;i--)if(sum[i]==n){Min=i;break;}ll ans=0,tmp=0;int flag=0;for(int i=Max;i>Min;){if(tmp+sum[i]<=k){tmp+=sum[i];i--;}else{flag=1;tmp=0;ans++;}}if(tmp!=0)ans++;cout<<ans<<endl;}return 0;
}