题解 P2672 【推销员】

scallop

2018-07-15 11:13:09

Solution

说下我的想法吧。 考虑一个人的贡献只可能是他自己的A以及他的位置D,我们考虑记录一下当前走的最远距离dist,那么一个人的贡献就应该是 $\max(0,2*(D_i-dist))+A_i$ 考虑分别按照$2*D+A$与$A$排序出两个数组,每次取出最大的没有被标记的点(只可能是两个数组的首位较大的那个),更新答案与$dist$, 并且打上标记。 考虑到两个数组里面的每个元素的贡献都是单调不增的,所以这样做应该是正确的。 这样复杂度为 $O(N\log N)$ PS:如果能被hack欢迎hack。 ```cpp #include <algorithm> #include <iostream> #include <fstream> #include <cstring> #include <cstdlib> #include <string> #include <cstdio> #include <vector> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <map> using namespace std; struct person { int p; int d; int v; bool operator = (const person &t) { p = t.p; d = t.d; v = t.v; } }; const int MAXN = 100000 + 10; int D; int n; person a[MAXN], b[MAXN]; bool visit[MAXN]; bool compare1(const person &a, const person &b) { return a.d + a.v > b.d + b.v; } bool compare2(const person &a, const person &b) { return a.v > b.v; } int read() { int x; scanf("%d", &x); return x; } int main() { n = read(); for (int i = 1; i < n + 1; ++i) { a[i].d = read(); a[i].d *= 2; } for (int i = 1; i < n + 1; ++i) { a[i].v = read(); a[i].p = i; b[i] = a[i]; } sort(a + 1, a + n + 1, compare1); sort(b + 1, b + n + 1, compare2); int i = 1, j = 1, k = 0, ans = 0; while (k < n) { while (i <= n && (visit[a[i].p] || a[i].d < D)) ++i; while (j <= n && visit[b[j].p]) ++j; if (a[i].d - D + a[i].v > b[j].v) { visit[a[i].p] = true; ans += a[i].d - D + a[i].v; D = max(D, a[i].d); } else { visit[b[j].p] = true; ans += b[j].v; } printf("%d\n", ans); ++k; } return 0; } ```