/ Vijos / 讨论 / 海港 /

为什么TLE?

70分做法为什么TLE,时间复杂度为O(人数+船数),应该不会超啊

2 条评论

  • @ 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 20:41:34

      map查找效率lgn,不是很高,改成数组T一个点,加入输入优化AC

    • @ 2017-02-17 13:48:09

      因为考场上开二维数组怕爆,所以开了个map,搬下来忘记改,已AC,谢谢大佬!

  • @ 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);
    }

    • @ 2017-02-16 16:54:03

      orz 我看错了

    • @ 2017-02-16 16:55:30
      1. 在Vijos上vector速度很慢,考虑替换掉它。
      2. 最好使用读入优化。
    • @ 2017-02-16 17:01:19

      他是加了读入优化的,另外我发现vj好像开不开标准输入输出缓冲区影响不大(这是由于评测机直接重定向标准输入输出到内存吧)。

      确实vector慢死了

    • @ 2017-02-16 17:19:34

      嗯,懂了,谢谢各位dalao

  • 1

信息

ID
2011
难度
4
分类
(无)
标签
递交数
900
已通过
249
通过率
28%
被复制
18
上传者