直接上题：
输出：
输出n行：
第i行输出一个整数表示第i艘船到达后的统计信息。
思路：
可以看到n非常之大
考虑时间复杂度：
| O(1) | O(log n) | O(n) | O(n^2) | O(n^3) |
| 蒟蒻暂时想不到O(1)的做法 | 蒟蒻太弱了这个也想不出来 | 不错 | TLE警告 | 别想了 |
所以目前时间复杂度符合的只有O(n) （输入必须要n*k没办法但是能AC别慌）
整体代码思路：
利用“”桶”的思想统计每个国籍有多少人
把队列和结构体结合到一起模拟统计表
就AC了……
可还有一些细节：
1.每一行的信息统计完之后不能清空，下一行是建立在第一行的基础上继续统计，除了出队之外没有任何剔除元素的位置
2.这题因数据量较大建议用scanf&printf，cin&cout容易TLE
上代码！
# include <iostream>
# include <cstdio>
# include <queue>
using namespace std;
# define N 100005
int n,book[N],cnt;
struct node{
int t,c;
};
queue <node> q;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
int t,k;
scanf("%d%d",&t,&k);
for (int j=1;j<=k;j++){
int coun;
scanf("%d",&coun);
book[coun]++;
if (book[coun]==1){
cnt++;
}
node a;
a.t=t;
a.c=coun;
q.push(a);
}
node a=q.front();
node b=q.back();
while(b.t-86400>a.t){
book[a.c]--;
if (book[a.c]==0){
cnt--;
}
q.pop();
a=q.front();
}
printf("%d\n",cnt);
}
return 0;
}70分（恼） ……
问题出在哪儿了呢？？
细节！纯纯的细节！
注意这个“内”字
什么意思呢？
统计表（队列）中应该只有86400秒之内的，刚好24小时的也要扔了
AC代码：
# include <iostream>
# include <cstdio>
# include <queue>
using namespace std;
# define N 100005
int n,book[N],cnt;
struct node{
int t,c;
};
queue <node> q;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
int t,k;
scanf("%d%d",&t,&k);
for (int j=1;j<=k;j++){
int coun;
scanf("%d",&coun);
book[coun]++;
if (book[coun]==1){
cnt++;
}
node a;
a.t=t;
a.c=coun;
q.push(a);
}
node a=q.front();
node b=q.back();
while(a.t<=b.t-86400){
book[a.c]--;
if (book[a.c]==0){
cnt--;
}
q.pop();
a=q.front();
}
printf("%d\n",cnt);
}
return 0;
}总结：
这题难度上就是普及组，一个模拟题
可细节多多，需多注意
制作不易，点个赞吧
版权声明：本文为lsy201009原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。