专栏文章

题解：P14234 [COI 2011] 河流 / RIJEKA

GGeorgeDeng
P14234题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhffqk
此快照首次捕获于
2025/12/02 02:28
3 个月前
此快照最后确认于
2025/12/02 02:28
3 个月前
查看原文
显然，我们不管怎么样都要从 00 走到 mm，所以如果是 li≤ril_i\le r_i 的我们就可以忽略不计，因为可以顺便把这些人带走，考虑 li>ril_i>r_i 的情况。
把 rir_i 当作线段的左端点，lil_i 当作线段的右端点。如果 ii 与 jj 有重合，说明可以把这两个一起带走。然后，我们找到这一次最左边的和最右边的，把这两个线段的端点作差加进答案里。注意答案还要再加上 mm，因为要从 00 到 mm。
然后这样就做完了，时间复杂度 O(nlog⁡n)O(n\log n)，瓶颈在于排序。
AC 代码：
CPP
#include <iostream>
#include <utility>
#include <algorithm>
#define int long long
#define endl '\n'
using namespace std;

int n,m;
pair<int,int> pp[300000];
int len;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        if(l>r){
            pp[++len] = make_pair(r,l);
        }
    }
    // cout<<endl;
    sort(pp+1,pp+1+len);//给线段按照左端点排序
    int r = 1;
    int l = 1;//左端点和右端点
    int ans = 0;
    while(l<=len){
        int maxr = pp[l].second;
        r = l;
        while(r<=len){//一直往右找，直到到头或者不重叠了
            // cout<<"Chk: "<<r<<' '<<maxr<<endl;
            if(pp[r].first>maxr) break;
            maxr = max(maxr,pp[r].second);//注意这里是取max，因为有完全重叠的情况
            r++;
        }
        ans+=(maxr-pp[l].first)*2;
        // cout<<pp[l].first<<' '<<maxr<<endl;
        l = r;
    }
    cout<<ans+m;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...