线上OJ：
一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1972 (opens in a new tab)
洛谷：https://www.luogu.com.cn/problem/P2672 (opens in a new tab)
AcWing：https://www.acwing.com/problem/content/466/ (opens in a new tab)
核心思想：
1、推销给每一个住户的疲劳值由两部分组成：
① 推销给住户的疲劳值 Ai ( < )；
② 从入口走到该住户再走回入口的疲劳值 2*Si（< ）
2、Ai 是每个住户都有的基本属性，都会参与计算。2*Si 只会在最远的 Si 处进行计算，其他 < Si 的可以在路过的时候推销，故 不是所有的 Si 都需要计算。（本条记为性质1）
先分析这道题，由于给的测试数据只有一个，而且非常水，所以我们自己随机构建一组测试数据用于分析。
假设把每个住户看成一个结构体（则可如下所示）。
node[i].pl 为只推销这一个住户所产生的疲劳值，则node[i].pl 的最大值即为当 X=1（仅推销一个住户时）的解。
struct Node{
int a, s; // a为Ai，s为Si
int pl; // 如果直接到该住户的疲劳值
int idx;// 记录该住户的编号
};
Node node[MAXN];我们构造一组测试数据，如下图,可以发现:
如果只推销给一个人（X=1），那么应该选 idx 为 5 的。因为输出的是5号的疲劳值 node[5].pl = 20+2*7 = 34。很明显，34 是所有的里面最大的。
如果要推销给两个人（X=2），那么除了5号，第二个该选谁？
假设候选人在5号的左侧，由 “性质1” 可知，左侧的住户由于 node[i].s < node[5].s ，故 s 都不参与最终疲劳值的计算，只有 node[i].a 参与计算。所以，如果在 左侧选，就选 node[i].a 最大的 1 号。因为 node[1].a = 10，是左侧剩余4个中最大的。
假设候选人在5号的右侧，则 node[i].s > node[5].s。所以右侧住户的 a 和 s 都要参与考虑。我们记右侧住户带来的 疲劳值增量 为 ， 其中 。由于若选择了更远的s（比如），则更远的 node[i].s 会包含原先的 node[i].5。所以，如果在 右侧选，就选 7 号。因为7号的增量为 9 + 2*(9-7) = 13，6号的增量为 3+2*（8-7）=5，8号的增量为 4 + 2*(11-7) = 12。7号的 增量最大。
综上所述，在左侧和右侧的最大值中挑一个最大的，即可作为下一轮的候选。
解法一的核心思想：
1、先找到初始疲劳值最大的住户，作为 X=1 时的结果，直接输出。同时记录该住户的序号 为 now
2、在 now 的左侧寻找 node[i].a 的最大值，作为左侧最大值 maxL；在 now 的右侧寻找 node[i].a + Δs 最大值，作为右侧最大值 maxR。
3、在 maxL 和 maxR 中取大者作为下一轮的选择。
a. 如果 maxL 更大，则输出 ，此时 now 不变。
b. 如果 maxR 更大，则输出 ，此时 now 的位置要迁移到更大的 si 处。
注意1：由于每次都是在now的左侧和右侧寻找最大值，所以可以考虑用 两个优先队列 分别存储左侧和右侧。每次只需要从优先队列的 top 取出合法的数值即可。
注意2：如果右侧的增量更大，则记得更新 now 的位置至新的 si。同时由于now的位置发生了变化， now左右两侧的优先队列都需要更新。
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
struct Node{
int a, s;
int pl; // 如果直接到该住户的疲劳值
int idx;// 记录该住户的编号
bool operator <(const Node &a)const{
return pl<a.pl;//以结构体中的ans（每一家推销的疲劳值）为比较对象
}
};
Node node[MAXN];
priority_queue<Node> qR;
priority_queue<int> qL;
int n, now, maxL, maxR, ans;
// 模拟。每次比较左侧最大值和右侧最大值。如果是右侧最大值，则更新now的位置
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", &node[i].s);
for(int i = 1; i <= n; i++) // 读入每个住户的a,s，疲劳值，以及索引号
{
scanf("%d", &node[i].a);
node[i].pl = 2 * node[i].s + node[i].a;
node[i].idx = i;
qR.push(node[i]); // 初始都加入右侧的qR优先队列
}
for(int i = 1; i <= n; i++)
{
maxL = maxR = 0;
if(!qL.empty())
maxL = qL.top(); // 如果now左侧不为空，则取出左侧最大的ai
if(!qR.empty()) // 将now右边的最大pl值取出
maxR = qR.top().pl;
if(maxL < maxR - 2 * node[now].s) // 如果右边的最大值更大 （由于右边的距离更远，所以更远距离产生的疲劳值要减去now位置的距离疲劳值，才是右边最大值带来的疲劳值增幅）
{
ans += maxR - 2 * node[now].s;// 当前输出结果加上右侧最大值的增幅
for(int k = now + 1; k < qR.top().idx; k++)
qL.push(node[k].a); // now和新位置所夹的住户疲劳值，都入左侧的优先队列
now = qR.top().idx; // 更新now的坐标，并从qR弹出
qR.pop();
while(!qR.empty() && qR.top().idx <= now)
qR.pop(); // 保证右侧优先队列的top是在新now的右边
}
else
{
ans += maxL; // 如果是左边的大，则输出结果直接加上maxL即可
qL.pop();
}
printf("%d\n", ans);
}
return 0;
}注：解法一的时间复杂度是 O(N2)，其实是有风险的。好在数据都过了，说明测试数据中并没有极端数据存在。