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

GeorgeDeng · 2025-10-27 17:46:27 · 题解

显然，我们不管怎么样都要从 0 走到 m，所以如果是 l_i\le r_i 的我们就可以忽略不计，因为可以顺便把这些人带走，考虑 l_i>r_i 的情况。

把 r_i 当作线段的左端点，l_i 当作线段的右端点。如果 i 与 j 有重合，说明可以把这两个一起带走。然后，我们找到这一次最左边的和最右边的，把这两个线段的端点作差加进答案里。注意答案还要再加上 m，因为要从 0 到 m。

然后这样就做完了，时间复杂度 O(n\log n)，瓶颈在于排序。

AC 代码：

#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;
}