洛谷P2672 推销员

url: https://www.luogu.com.cn/problem/P2672

tag:
NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。

思路：
思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输出即可。如何求呢？这里用动态规划和前缀和来求，具体可以看代码。看其他题解有用线段树来做，但是比较麻烦，就上动规和前缀和了。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
long long sum[N], c[N], h[N];
struct client {
    int s, a;
}Client[N];
bool cmp(client &a, client &b)
{
    return a.a > b.a;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) cin >> Client[i].s;
    for (int i = 1; i <= n; i ++) cin >> Client[i].a;
    sort(Client + 1, Client + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
    {
        sum[i] = sum[i - 1] + Client[i].a;
        h[i] = max(h[i - 1], (long long)Client[i].s * 2);
    }
    for (int i = n; i >= 1; i --)
    {
        c[i] = max(c[i + 1], 2LL * Client[i].s + Client[i].a);
    }
    for (int i = 1; i <= n; i ++)
    {
        cout << max(sum[i] + h[i], sum[i - 1] + c[i]) << '\n';
    }
    return 0;
}