CSP历年复赛题-P2672 [NOIP2015 普及组] 推销员

原题链接：https://www.luogu.com.cn/problem/P2672

题意解读：N家住户，每家住户与出入口距离是Si米，推销员每走1米疲劳值+1，向第i家住户推销疲劳值+Ai，推销员推销完原路返回出口，计算在向不同数量X的住户推销时，能达到的最大疲劳值。

解题思路：

本题是一种贪心选择问题，需要思考出可能的最优解，并取最大值。

最直观的思路，要计算给X个住户推销的最大疲劳值，取前X个疲劳值最大的住户即可，这样“总的疲劳值=x个最大疲劳值之和+前x住户最远距离*2”

但还有一种可能，如果在前X个最大疲劳值住户里，去掉一个疲劳值最小的，换一家在X以后的住户里“距离*2+疲劳值”最大的，这样总的疲劳值是可能更大的，这是“总的疲劳值=(X之后距离*2+疲劳值最大值) + 前X-1个最大疲劳值之和”

对以上两种情况计算的总疲劳值求max即可

为了加速“前x个最大疲劳值之和”，“前x个住户最远距离”，“x之后的距离*2+疲劳值最大值”的计算，可以定义三个数组并提前预处理：

p[i]：前i个最大的疲劳值Ai之和

s[i]：前i个最大的疲劳值住户中最远的距离

w[i]：第i个之后的住户“距离*2+疲劳值”最大值

预处理以上数组之后，x从1枚举到n，每次计算两种疲劳值并取max：

max(p[x] + s[x] * 2, w[x] + p[x-1])

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct node
{
    int s, a;
};
node q[N];
int n;
int p[N]; //p[i]：前i个最大的疲劳值Ai之和
int s[N]; //s[i]：前i个最大的疲劳值住户中最远的距离
int w[N]; //w[i]：第i个之后的住户“距离*2+疲劳值”最大值

bool cmp(node q1, node q2)
{
    return q1.a > q2.a; //按疲劳值从大到小排序
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> q[i].s;
    for(int i = 1; i <= n; i++) cin >> q[i].a;

    sort(q + 1, q + n + 1, cmp);

    for(int i = 1; i <= n; i++) p[i] = p[i-1] + q[i].a;
    for(int i = 1; i <= n; i++) s[i] = max(s[i-1], q[i].s);
    for(int i = n; i >= 0; i--) w[i] = max(w[i+1], q[i].s * 2 + q[i].a);

    for(int x = 1; x <= n; x++) cout << max(p[x] + s[x] * 2, w[x] + p[x-1]) << endl;
}