- 海港
- 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;
c++
主要代码
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
- 分类
- (无)
- 标签
- 递交数
- 901
- 已通过
- 250
- 通过率
- 28%
- 被复制
- 19
- 上传者