题解 P2672 【推销员】

说下我的想法吧。 考虑一个人的贡献只可能是他自己的A以及他的位置D,我们考虑记录一下当前走的最远距离dist,那么一个人的贡献就应该是 $\max(0,2*(D_i-dist))+A_i$

考虑分别按照$2*D+A$与$A$排序出两个数组,每次取出最大的没有被标记的点(只可能是两个数组的首位较大的那个),更新答案与$dist$, 并且打上标记。

考虑到两个数组里面的每个元素的贡献都是单调不增的,所以这样做应该是正确的。

这样复杂度为 $O(N\log N)$

PS:如果能被hack欢迎hack。

#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;
}

发表于 2018-07-15 11:13:09 in 题解