CSU 1684-Disastrous Downtime

题目链接:https://nanti.jisuanke.com/t/28879

思路:贪心，从最早收到请求的时刻开始,统计每个相差1000毫秒的时间段内接收的请求数量再计算该时间段内所需机器数目,答案就是所有时间段中最大的机器数目

 1 #include<iostream>
 2 #define inf 0x3f3f3f3f
 3 using namespace std;
 4 int a[101000];
 5 int main()
 6 {
 7     int n,k,maxx=0,minn=inf;
 8     cin>>n>>k;
 9     for(int i=0;i<101005;i++)
10     a[i]=0;
11     for(int i=0;i<n;i++)
12     {
13         int t;
14         cin>>t;
15         maxx=max(t,maxx);
16         minn=min(t,minn);
17         a[t]++;
18     }
19     int ans=0,cnt,num;
20     for(int i=minn;i<=maxx;i+=1000)
21     {
22         cnt=0,num=0;
23         for(int j=0;j<1000;j++)
24         if(a[i+j])
25         num+=a[i+j];
26         if(num<=k)cnt=1;
27         else
28         {
29             cnt=num/k;
30             if(num%k)cnt++;
31         }
32         ans=max(ans,cnt);
33     }
34     cout<<ans<<endl;
35     return 0;
36 }