专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minl2gzt
此快照首次捕获于
2025/12/02 04:10
3 个月前
此快照最后确认于
2025/12/02 04:10
3 个月前
查看原文
吐槽一下：一开始这题的样例 22 错了，导致我算了半个多小时。
这里有两种情况：
  1. 顺着一开始的方向走，即目标村庄大于出发村庄。由于我们最后是要到 mm 的，那么这种情况就直接走，不需要额外算，所以下文就忽略这种情况。
  2. 逆着一开始的方向走，即出发村庄大于目标村庄。贪心的主要部分就是这种情况。
那么如何贪心的走第二种情况呢？
首先要搞清楚要怎么贪心。原本如果直接按照输入的方式走的话，每次遇到第二次情况就会拐回去，这样就会导致多走，所以说我们就是要贪心的选取拐弯点。
但是该怎么选取拐弯点呢？
我们先按出发村庄进行排序，这样就能确定上船顺序。
我们选取一个乘客 ii ，和在 ii 乘客后面第一个上船的乘客 jj 。
我们记 ii 乘客的出发村庄为 xrx_r，目标村庄为 xlx_l ，jj 乘客的出发村庄为 yry_r，目标村庄为 yly_l。
如果从 ii 乘客的出发村庄 xrx_r 开始拐弯，将两名乘客都送到的路程是：
(yr−xl)+2(xr−xl)+2(yr−yl)(y_r-x_l)+2 (x_r-x_l)+2 (y_r-y_l)
整理一下得：
3(yr−xl)+2(xr−yl)3(y_r-x_l)+2(x_r-y_l)
而如果不在 ii 乘客的出发村庄 xrx_r，而是从jj 乘客的出发村庄 yry_r，将两名乘客都送到的路程是：
3(yr−xl)3 (y_r-x_l)
那么发现两种情况的大小关系取决于 xrx_r 和 yly_l 的大小关系，那么分类讨论。
当 xr≥ylx_r \ge y_l 时，jj 乘客的出发村庄 yry_r 拐弯更省路，否则从 ii 乘客的出发村庄 xrx_r 开始拐弯更省。
这样我们维护一个指针，每次从这个指针开始往后枚举拐弯点即可。
Code:
CPP
#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;
}

评论

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

正在加载评论...