P2672 [NOIP2015 普及组] 推销员

难度： 提高+/省选- 。

考点：贪心、前缀和。

题意：

​ $n$ 个住户，小明每走一米消耗 $1$ 疲劳，第 $i$ 个住户距离起点 $S_i$ 米，同时走进住户沟通会累积 $A_i$ 疲劳。问如何在不走多余的路前提下，他 最多可以累积 多少点疲劳值？

分析：

​ $n\le 10^5$ 考虑贪心和 DP。

​ 而关联到疲劳值消耗最大，应该要从 $\sum A$ 和 $2S$ 来考虑，假设选择了 $x$ 名住户，分别代表所选择的 $x$ 个住户的情况下，沟通带来的疲劳值之和 $\sum A$，以及所选择住户中最远的住户距离 $S$ 有关。

​ 想让所选择的 $x$ 个住户的情况下消耗最大，其中距离 $S、A$ 都是固定的，那么应该要让 $x-1$ 个住户的消耗最大。

​ 假设我们选择了最大的 $A_i$ 的 $x$ 名的顾客， $A_1,A_2,...,A_x$，其中距离来看 $S_1<...<S_{x-1}<S_x$，假设我们换成了 $k$ 个最大的 $A_i$，$A_1,A_2,...,A_k$，其中距离来看 $S_1<...<S_{k-1}<S_k$。已经知道 $1\sim x$ 个顾客是前 $x$ 个大的 $A_i$，那么替换的 $k$ 个只能是在这 $x$ 里面去取，如果替换的 $k$ 个中最大的距离是 $S_k$ 那么 $S_k\le S_x$，所以选择的前 $x$ 大的 $A_i$ 答案不会更劣。如下图为 $S_x$ 为最远端所选择的住户位置：

​ 那么服务的住户肯定是选择的前 $x$ 大的位置，其他选择的位置也不会是最优解。

​ 计算贡献：$\sum A+2S$ 中可能会出现两种选择的情况，选择的 $A$ 较大或者 $S$ 较远的住户都有可能，因为任意一种只要 足够大/远 就可以影响选择的可能性。

本题的核心性质：

向 $x$ 家住户推销产品的最大话费只有两种情况：推销给 $A_i$ 最大的 $x$ 家；或者推销给 $A_i$ 最大的 $x-1$ 家，然后最后一家尽可能远。

​ 因此可以先讲所有住户按 $A_i$ 从大到小排序，利用前缀和思想与处理出三个数组：

• f[i] 表示前 $i$ 个 $A_i$ 的和；
• g[i] 表示前 $i$ 个 S_i 的最大值；
• h[i] 表示 $i\sim n$ 中 $2S_i+A_i$ 的最大值；

​ 那么向 x 家住户推销产品的最大话费就是下面两种情况的最大值：

• 推销给 $A_i$ 最大的 $x$ 家：f[i] + 2 * g[i]；
• 推销给 $A_i$ 最大的 $x-1$ 家，然后最后一家尽可能远：f[i-1] + h[i]；

时间复杂度：

​ 预处理前缀和数组求每个 $x$ 对应的最大话费都是线性的，再加上排序，总时间复杂度是 $O(nlogn)$。

参考代码：

#include <bits/stdc++.h>
#define ll long long
#define PII std::pair<int, int>const int N = 1e5 + 10;
int f[N], g[N], h[N], n;
PII p[N];int main()
{std::ios::sync_with_stdio(false), std::cin.tie(nullptr);std::cin >> n;for (int i = 1; i <= n; i++)std::cin >> p[i].second; // si 距离for (int i = 1; i <= n; i++)std::cin >> p[i].first; // ai 疲劳值// 贪心策略：按照疲劳值从大到小排序sort(p + 1, p + 1 + n, std::greater<PII>());// 扫一遍，维护前 i 大的住户信息 ::: f[i]: 前 1~i 的 sum(Ai) , g[i]: 前 1~i 中最远的 max(Si)for (int i = 1; i <= n; i++){f[i] = f[i - 1] + p[i].first;g[i] = std::max(g[i - 1], p[i].second);}// 贪心策略2：贪心维护，i 位置上，靠后的住户的最大贡献值 h[i] : ( Sum(Ai) + 2Si)for (int i = n; i; i--)h[i] = std::max(h[i + 1], p[i].first + p[i].second * 2);// 比较两种情况// 情况一：直接选择最大的 x 名住户。// 情况二：去掉第 i 位住户( A 最小贡献)，取前 1~i-1 个住户(最大疲劳和) sum(A(i-1)) + 贪心(后面的某位较大的贡献)的住户 Ai+2Si。for (int i = 1; i <= n; i++)std::cout << std::max(f[i] + g[i] * 2, f[i - 1] + h[i]) << "\n";return 0;
}