https://codeforces.com/contest/1503
C. Travelling Salesman Problem
题意：有 n ，2≤n≤105 座城市，有魅力值 ai，最低票价 ci，现在从 1 号城市出发，经过每个城市恰一次，最终回到 1 号城市，从 i 到 j 的代价等于 max(ci,aj−ai)，0≤ai,ci≤109。问最少总代价。
思维+贪心
首先要发现路径是个环，所以从哪个城市出发都是一样的，无非就是环从哪里断开。
要经过所有城市恰一次，那么 ∑ci 是至少的。因此先把 ∑ci 加到答案里，这样从 i 到 j 的代价就变成了 max(0,aj−ai−ci)。
再发现如果 aj<ai，那么从 i 到 j 的代价就必定等于 ci，如果所有路径都满足出发地的 a 值更大，那么最终答案就是下限 ∑ci。
把所有城市按照 ai 排序，从右边向左边走是免费的（即代价为 ci，已经统一加进答案）。但是因为路径是环形的，所以必定还要有从 1 到 n 的一条路径，这就使得答案可能大于下限。
从左向右走代价为：若 aj>ai+ci，则为 aj−(ai+ci)。否则为 0。
考虑如果直接从 1 走到 n。若 an>a1+c1，则答案为 an−a1−c1；若 an≤a1+c1，则答案就等于下限，这种情况就不讨论了。
假设从 1 走到 u，再走到 n，且这两段都不免费，则答案为 an−au−cu+au−a1−c1，即 an−a1−c1−cu 那么显然这种方案比直接从 1 走到 n 代价更低。
所以策略就是从 1 走到 n，中间尽量多走不免费的边，有点反直觉，但是可以理解为原来是走一条从 1 到 n 的大边，这条边代价太高，所以分解成尽量多条小的边。
走一条边的代价为 aj−(ai+ci)，最终代价等于 ∑aj−(ai+ci)，所以显然对于一个目标点 j，要从前面所有点中 ai+ci 最大的点作为出发点走过来。
下面用 i 代表当前路径上 a+c 最大的点。
很巧的是，i 一定是当前贪心选择的这条路径到目前为止的终点，也就是说不会发生它已经连到其它点的情况。证明：当 aj>ai+ci 时，必定走 (i,j) 这条边，而 aj+cj 一定大于 ai+ci，也就是说目标点 j 一定会变成新的 a+c 最大的点。
还要注意到当 aj≤ai+ci 时也是可能会走到 j 的，这时虽然对答案没有贡献，但是如果它的 aj+cj>ai+ci，那么它就成为了新的 a+c 最大的点，因此以后也是需要以它作为出发点的，所以要加进路径中。要注意这不代表所有点都能加进路径里，因为其它对答案没有贡献的点如果作为出发点，就不能保证 a+c 最大的点是当前路径的终点，也就不能保证能连到这个 a+c 最大的点了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
struct X
{
ll a, c;
bool operator<(const X& b)const {
return a < b.a;
}
}t[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &t[i].a, &t[i].c);
}
sort(t + 1, t + n + 1);
ll ans = 0, mx = t[1].a + t[1].c;
for (int i = 1; i <= n; i++) {
ans += t[i].c;
if (t[i].a > mx) {
ans += t[i].a - mx;
}
mx = max(mx, t[i].a + t[i].c);
}
printf("%lld\n", ans);
return 0;
}
|
