题意：N台请求，每台机器1秒能处理K个，处理一个需要耗时1s，给出每个请求的出现时间，问至少需要几个机器才能全部处理？
思路：把每个请求的时间看成一个区间，比如在0时间点出现，则它占用机器的时间为[0,1000）
为了简化，我们直接写成占用区间为[i,i+999]
只要某一个点的覆盖数未超过K，则一台机器就能应付
所以问题转化为求区间最大覆盖数，答案为ceil(最大覆盖数/k)
这里有个小技巧：ceil(n/k)=(n-1)/k+1
#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #define ll long long #define mems(a,b) memset(a,b,sizeof(a)) #define ls pos<<1 #define rs pos<<1|1using namespace std; const int MAXN = 1e5+5; const int MAXE = 100005; const int INF = 0x3f3f3f3f;struct Node{int l,r,cov,lazy; }node[MAXN<<2];int n,m,k; int a[MAXN];void build(int l,int r,int pos){node[pos].l=l;node[pos].r=r;node[pos].cov=0;node[pos].lazy=0;if(l==r) return;int mid=(l+r)>>1;build(l,mid,ls);build(mid+1,r,rs); }void pushdown(int pos){if(node[pos].lazy){node[ls].cov+=node[pos].lazy;node[rs].cov+=node[pos].lazy;node[pos].lazy=0;} }void update(int l,int r,int pos){if(l<=node[pos].l&&node[pos].r<=r){node[pos].cov++;node[pos].lazy++;return;}pushdown(pos);int mid=(node[pos].l+node[pos].r)>>1;if(l<=mid) update(l,r,ls);if(r>mid) update(l,r,rs);//cout<<node[pos].maxc<<'\t'<<node[ls].maxc<<'\t'<<node[rs].maxc<<endl;node[pos].cov=max(node[ls].cov,node[rs].cov); }int main(){while(~scanf("%d%d",&n,&k)){m=-1;for(int i=0;i<n;i++){scanf("%d",&a[i]);m=max(a[i],m);}build(0,m+1000,1);for(int i=0;i<n;i++) update(a[i],a[i]+999,1);//cout<<node[1].l<<'\t'<<node[1].maxc<<endl;cout<<(node[1].cov-1)/k+1<<endl;}return 0; }