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

yueyan_WZF · 2025-10-17 16:55:22 · 题解

吐槽一下：一开始这题的样例 2 错了，导致我算了半个多小时。

这里有两种情况：

1. 顺着一开始的方向走，即目标村庄大于出发村庄。由于我们最后是要到 m 的，那么这种情况就直接走，不需要额外算，所以下文就忽略这种情况。
2. 逆着一开始的方向走，即出发村庄大于目标村庄。贪心的主要部分就是这种情况。

那么如何贪心的走第二种情况呢？

首先要搞清楚要怎么贪心。原本如果直接按照输入的方式走的话，每次遇到第二次情况就会拐回去，这样就会导致多走，所以说我们就是要贪心的选取拐弯点。

但是该怎么选取拐弯点呢？

我们先按出发村庄进行排序，这样就能确定上船顺序。

我们选取一个乘客 i ，和在 i 乘客后面第一个上船的乘客 j 。

我们记 i 乘客的出发村庄为 x_r，目标村庄为 x_l ，j 乘客的出发村庄为 y_r，目标村庄为 y_l。

如果从 i 乘客的出发村庄 x_r 开始拐弯，将两名乘客都送到的路程是：

整理一下得：

而如果不在 i 乘客的出发村庄 x_r，而是从j 乘客的出发村庄 y_r，将两名乘客都送到的路程是：

那么发现两种情况的大小关系取决于 x_r 和 y_l 的大小关系，那么分类讨论。

当 x_r \ge y_l 时，j 乘客的出发村庄 y_r 拐弯更省路，否则从 i 乘客的出发村庄 x_r 开始拐弯更省。

这样我们维护一个指针，每次从这个指针开始往后枚举拐弯点即可。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct node{
    int l,r;
}z[1000004];
int tot;
bool cmp(node x,node y){
    if(x.l==y.l) return x.r<y.r;
    return x.l<y.l;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>z[++tot].l>>z[tot].r;
        if(z[tot].r>z[tot].l) tot--;
        else swap(z[tot].l,z[tot].r);
    }
    sort(z+1,z+1+tot,cmp);
    int ans=0;
    z[tot+1].l=1e18,z[tot+1].r=1e18;
    for(int i=1;i<=tot;i++){
        int j=i,maxx=z[j].r;
        while(z[j+1].l<=maxx&&j<tot){
          j++;
          maxx=max(maxx,z[j].r);
        }
        ans+=2*(maxx-z[i].l);
        i=j;
    }
    cout<<ans+m<<endl;
}