社区讨论

TLE谜题

P1514[NOIP 2010 提高组] 引水入城参与者 5已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi6m7c6l
此快照首次捕获于
2025/11/20 07:09
4 个月前
此快照最后确认于
2025/11/20 07:09
4 个月前
查看原帖
区间覆盖原代码:
CPP
    sort(dp+1,dp+m+1);
    int k=1,last=1,res=0;
    while(last<m)
    {
        int temp=0;
        while(dp[k].first<=last)
        {
            temp=max(temp,dp[k].second);
            k++;
        } 
        last=temp;
        res++;
    }
超过1000ms
仅将这部分代码改成:
CPP
    int left=1,res=0;
    while (left<=m){
        int maxr=0;
        for (int i=1;i<=m;i++)
            if (cov[1][i].first<=left)
                maxr=max(maxr,cov[1][i].second);
        res++;
        left=maxr+1;
    }
只要12ms
从复杂度来说至少没有提升
难道是luogu的评测机一跑sort就炸???

回复

8 条回复,欢迎继续交流。

正在加载回复...