∆ 首先，这是一道贪心的绝世好题

§ 其次，这道题要用到结构体这门高深的知识

☆ 最后，这道题我样例2没有过但是我交了4个OJ都AC了

??????????????????_______????????????????????

---

不bb了，上思路吧

这道题主要用到了瞪眼大法以及贪心大法

我们可以记录下往返距离加上自身疲劳值最高的一个崽儿，以下就简称ze。

然后通过观察样例，可以发现ze每次都会参与输出，即每次都会向ze这个点进行推销，但不一定每次都把ze这个点当作终点。因为我们的排序规则是往返距离加上自身疲劳值按降序进行排序，所以ze不一定就是最远的那一户人家。

通过以上的瞪眼观察，我们发现，既然每一次都会有ze这个点，那么我们就可以划分子问题了，符合了贪心的定义。

其实这个思路也不是我独立思考出来的，而是我们机房大佬写了一篇题解。 但是这篇题解简直不要太精简，我是完全没有看懂。而代码我也没有去看

§ 给大家观摩一下:

一道贪心的题

其实找到距离较远但疲劳值(往返+当前位置的疲劳值）最大的那个位置

让它C位出道

再排序排出疲劳值高的

前缀和+当前最远距离*2

---

不知道大家看懂没有，反正我这个人一向看不懂别人的思路。不过这也给了我一点启发

Q:为什么不用DP？

A:因为DP会超时，而且看这道题目只是15年普及组的T3，用不着

你们最爱的完整代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define Inf 0x3f3f3f3f

using namespace std;

const int MAXN = 100000 + 5;
struct Node {
	int Far, Cost;
} a[MAXN];
int n, maxValue, list[MAXN];
inline bool Rule(const Node &a, const Node &b)
	{ return ((a.Cost == b.Cost) && (a.Far > b.Far)) || (a.Cost > b.Cost); }

signed main() {
	scanf("%d", &n);
	for (register int i = 1; i <= n; ++i) scanf("%d", &a[i].Far);
	for (register int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].Cost);
		if ((a[i].Far << 1) + a[i].Cost > (a[maxValue].Far << 1) + a[i].Cost)
			maxValue = i;
	}
	
	a[0] = a[maxValue];
	a[maxValue] = Node{-Inf, -Inf};
	stable_sort(a + 1, a + 1 + n, Rule);

	for (register int i = 0; i < n; ++i)
		list[i] = max(list[i - 1], a[i].Far);
	int and_ = 0;
	for (register int i = 0; i < n; ++i) {
		and_ += a[i].Cost;
		printf("%d\n", and_ + (list[i] << 1));
	}
	return 0;
}