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

ksmgxeh · 2025-11-22 22:59:20 · 题解

把乘客分成两类。第一类是起点小于终点的，第二类是起点大于终点的。对于第一类乘客，在一次从 0 到 M 的旅行中肯定可以一次性满足所有乘客的需求。

对于第二类乘客，我们需要走回头路。考虑如何让总代价最小，不难发现应把那些路线有交集的乘客在一次回头中全部送到。于是我们把第二类乘客单独挑出来排序，求一遍线段并，记其长度为 s。答案为 M+2\times s。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N = 3e5+5;
int n,m,cnt;
struct node{
  int x,y;
  bool operator <(const node &a) const{
    return x<a.x;
  }
}a[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
      int x,y; cin>>x>>y;
      if(x<y) continue;
      a[++cnt]={x,y};
    }
    a[++cnt]={0,0};
    sort(a+1,a+cnt+1);
    ll sum=m,s=2e9,t=2e9;
    for(int i=cnt;i>=1;i--){
      if(a[i].x<t){
        // cout<<s<<' '<<t<<"\n";
        sum+=2*(s-t);
        s=a[i].x,t=a[i].y;
      }else if(a[i].y<t) t=a[i].y;
    }
    cout<<sum;
    return 0;
}