考察:模拟
错误思路:
完全按题目意思走,暴力模拟.时间复杂度O(1010) ,TLE
正确思路:
压缩处理,记录商店上次处理的时间,用本次的时间-上次处理的时间-1,就是到本次时间该商店应该-1的次数,因为每次都是减去相同的数,所以可以压缩到一起.同理,在某一时刻可能会有多份相同的订单,我们也压缩一并处理.
最后计算答案时,如果上次处理的时间<T,说明我们还需要在T时间处理一下.
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int N = 100010; 6 typedef pair<int,int> PII; 7 int n,m,T,score[N],last[N]; 8 bool st[N]; 9 PII p[N]; 10 int main() 11 { 12 scanf("%d%d%d",&n,&m,&T); 13 for(int i=1;i<=m;i++) scanf("%d%d",&p[i].first,&p[i].second); 14 sort(p+1,p+m+1); 15 for(int i=1,j=1;i<=m;i++) 16 { 17 while(j<=m&&p[i]==p[j]) j++;//将订单号相同的一起处理 18 int t = p[i].first,id = p[i].second;//j代表第一个与i不同的 19 score[id]-=t-last[id]-1;//本次时间-上次处理订单的时间 20 if(score[id]<0) score[id] = 0; 21 if(score[id]<=3) st[id] = 0; 22 last[id] = t; 23 score[id]+=(j-i)*2; 24 i = j-1; 25 if(score[id]>5) st[id]=1; 26 } 27 for(int i=1;i<=n;i++) 28 { 29 if(last[i]<T) 30 { 31 score[i]-=T-last[i]; 32 if(score[i]<=3) st[i] = 0; 33 } 34 } 35 int ans = 0; 36 for(int i=1;i<=n;i++) ans+=st[i]; 37 printf("%d\n",ans); 38 return 0; 39 }