Codeforces Round /#712 (Div. 2) E. Travelling Salesman Problem

题目地址

https://codeforces.com/contest/1504/problem/E

题目大意

有n(1e5)个城市，每个城市有ai和ci两个属性，从城市i到城市j的费用为$max(c_i,a_j-c_i)$,问从任一城市开始经过所有城市再回到该城市所需要的最小费用。

解法

分析

我们观察这条式子：$cost(i,j)=max(c_i,a_j-c_i)$,可以知道$c_i$是逃不掉的，因此我们把c全部都先加到结果$res$上，这样每条边的费用就变成了$cost(i,j)=max(0,a_j-(a_i+c_i))$。

我们可以形象地把ai理解成楼房的高度，ci理解成这个楼房的梯子高度，我们在楼房i上时，如果楼房高度和梯子高度之和高于楼房j的高度，则可以免费从i爬到j，否则则需要补上这些高度的差。即从楼高+梯子较高的楼房爬到低的是不需要费用的。

解

以a为第一关键字，c为第二关键字对房子排序。

因此我们分两部分：

第一部分先从最低的楼层爬到最高的楼层（中间使费用尽量小）。

第二部分只需要把没爬过的楼房从高往低排列，最后走回最低的楼房即可（这部分不需要任何费用）。

int now = ac[1].ft+ac[1].sd;//now是当前房子+梯子的高度
   //之后每步的消耗看作max(0,aj-(ai+ci))
   rep(i,2,n){
       if(ac[i].ft>=now)//通过梯子上去的情况
           res += ac[i].ft-now;
       //不加的这些是达到最高之后访问的
       //如果这个楼可以使now更高，也应该在中间免费经过
       now = max(now,ac[i].ft+ac[i].sd);
   }
   //第二部分经过的楼全部免费

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
ll gcd(ll a,ll b){ while(b^=a^=b^=a%=b); return a; }
int n;
typedef pair<int,int> pii;
#define mkp make_pair
#define ft first
#define sd second
const int MAXN = 114514;
pii ac[MAXN];
ll res;
void solve(){
    res = 0;
    cin>>n;
    rep(i,1,n) cin>>ac[i].ft>>ac[i].sd,res+=ac[i].sd;
    sort(ac+1,ac+1+n);
    int now = ac[1].ft+ac[1].sd;//now是当前房子+梯子的高度
    //之后每步的消耗看作max(0,aj-(ai+ci))
    rep(i,2,n){
        if(ac[i].ft>=now)//通过梯子上去的情况
            res += ac[i].ft-now;
        //不加的这些是达到最高之后访问的
        //如果这个楼可以使now更高，也应该在中间免费经过
        now = max(now,ac[i].ft+ac[i].sd);
    }
    //第二部分经过的楼全部免费
    cout<<res<<endl;
}

int main(){
    solve();
}