- 海港
- @ 2017-02-16 09:40:21
70分做法为什么TLE,时间复杂度为O(人数+船数),应该不会超啊
2 条评论
- 
  lrj124 LV 10 @ 2017-02-16 20:15:15我的queue TLE 
 ```c++
 评测结果
 编译成功测试数据 #0: Accepted, time = 0 ms, mem = 736 KiB, score = 5 
 测试数据 #1: Accepted, time = 0 ms, mem = 736 KiB, score = 5
 测试数据 #2: Accepted, time = 0 ms, mem = 736 KiB, score = 5
 测试数据 #3: Accepted, time = 0 ms, mem = 736 KiB, score = 5
 测试数据 #4: Accepted, time = 0 ms, mem = 736 KiB, score = 5
 测试数据 #5: Accepted, time = 0 ms, mem = 736 KiB, score = 5
 测试数据 #6: Accepted, time = 0 ms, mem = 736 KiB, score = 5
 测试数据 #7: Accepted, time = 15 ms, mem = 736 KiB, score = 5
 测试数据 #8: Accepted, time = 15 ms, mem = 772 KiB, score = 5
 测试数据 #9: Accepted, time = 15 ms, mem = 772 KiB, score = 5
 测试数据 #10: Accepted, time = 31 ms, mem = 772 KiB, score = 5
 测试数据 #11: Accepted, time = 15 ms, mem = 772 KiB, score = 5
 测试数据 #12: Accepted, time = 15 ms, mem = 768 KiB, score = 5
 测试数据 #13: Accepted, time = 15 ms, mem = 776 KiB, score = 5
 测试数据 #14: TimeLimitExceeded, time = 1015 ms, mem = 3272 KiB, score = 0
 测试数据 #15: TimeLimitExceeded, time = 1015 ms, mem = 3672 KiB, score = 0
 测试数据 #16: TimeLimitExceeded, time = 1015 ms, mem = 3592 KiB, score = 0
 测试数据 #17: TimeLimitExceeded, time = 1015 ms, mem = 3824 KiB, score = 0
 测试数据 #18: TimeLimitExceeded, time = 1015 ms, mem = 3524 KiB, score = 0
 测试数据 #19: TimeLimitExceeded, time = 1015 ms, mem = 3508 KiB, score = 0
 TimeLimitExceeded, time = 6211 ms, mem = 3824 KiB, score = 70
 代码
 #include <cstdio>
 #include <queue>
 #include <map>
 using namespace std;
 map<int,int> vis;
 int n,ans = 0;
 struct Queue { int t,x; };
 queue<Queue> Q;
 int main() {
 //freopen("port.in","r",stdin);
 //freopen("port.out","w",stdout);
 scanf("%d",&n);
 for (int i = 1;i <= n;i++) {
 int t,k;
 scanf("%d%d",&t,&k);
 for (int i = 1,x;i <= k;i++) {
 scanf("%d",&x);
 if (!vis[x]) ans++;
 vis[x]++;
 Q.push((Queue){t,x});
 }
 while (true) {
 Queue head = Q.front();
 if (t-86400+1 <= head.t && head.t <= t) break;
 else {
 vis[head.x]--;
 if (!vis[head.x]) ans--;
 Q.pop();
 }
 }
 printf("%d\n",ans);
 }
 return 0;
 }
 ```
- 
  @ 2017-02-16 16:42:35用队列处理船,head和tail双指针,不是等于扫了两遍船O(2*n) 
 也有可能是我想错了
 ```c++struct chuan 
 {
 long ti;
 long ki;
 vector<long> people;
 };
 chuan p[100005];
 int ans=0;
 
 主要代码
 
 int head=0;
 int tail=0;
 for(int tail=0; tail<n; tail++) //n是船数
 {
 int len=p[tail].people.size();
 for(int i=0; i<len; i++)
 {
 if(num[p[tail].people[i]]==0) ans++; //num【i】是国籍 i 出现的次数
 num[p[tail].people[i]]++;
 }
 while(p[head].ti<=p[tail].ti-86400)
 {
 int len2=p[head].people.size();
 for(int i=0; i<len2; i++)
 {
 if(num[p[head].people[i]]==1) ans--;
 num[p[head].people[i]]--;
 }
 head++;
 }
 printf("%d\n",ans);
 }
- 1
信息
- ID
- 2011
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 903
- 已通过
- 252
- 通过率
- 28%
- 被复制
- 19
- 上传者