题解 P2672 【推销员】
scallop
2018-07-15 11:13:09
说下我的想法吧。
考虑一个人的贡献只可能是他自己的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;
}
```