Educational Codeforces Round 52 (Rated for Div. 2) -C

时间:2022-11-17 21:41:36

  

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define rep(i,j,k) for(long long i=j;i<=k;i++)
#define per(i,j,k) for(long long i=j;i>=k;i--)
using namespace std;
const int N = 2e5+5;
ll h[N];
int main(){
  long long n,k;
  while(~scanf("%lld%lld",&n,&k)){
      memset(h,0,sizeof(h));
      ll maxx=0;
      ll x;
      ll minn=2e5+5;
      for (int i=1;i<=n;i++){
          scanf("%lld",&x);
          h[x]++;
          minn=min(minn,x);
          maxx=max(maxx,x);
      }
      ll sum=0;
      per(i,maxx-1,minn)
      h[i]=h[i+1]+h[i];
      int cnt=0;
//      cout<<endl;
//      rep(i,minn,maxx){
//        printf("%d ",h[i]);
//      }
//      cout<<endl;
      per(i,maxx,minn){
          if (h[i]+sum>k){
            cnt++;
            sum=h[i];
          }else{
            sum=sum+h[i];
          }
      }
      if (sum>h[minn]){
       cnt++;
      }
      printf("%d\n",cnt);
  }
  return 0;
}