题解 P2672 【推销员】
-
前言
是介个样子，不知道是不是我太弱了，我看了好多题解，然后花了好多时间才明白贪心具体。
于是我决定自己写一题解，会详细一些的。本题解会有 贪心思路+例子模拟贪心
我觉得我挺有良心的,,希望大家都能看懂QAQ
-
题目大意
推销员阿明，要给住在某街的N个用户推销，走一米会增加1的疲劳值，第i家距离路口
s[i] 米(可能会有重复的s[i] )给第i家推销会增加a[i] 。全部推销完，还要原路返回。现在，依次向
X 用户推销，对于不同的X ，阿明想知道最大疲劳值
-
分析
距离是真的烦人，那就不管他吧。因为想要疲劳值最大，那么先按照疲劳值从大到小排序一边。
此时，可以判断出，最大值可能为：对于每个
X ，只要加上前X 大的疲劳值，再加上这些数中距离最远的并乘以2，也就是：sum(a[k])(1≤k≤X)+s[j]*2 其中，
s[j] 表示前K个距离最远的，sum()表示和。但是，推销员可以通过走远一点，虽然疲劳值比前面小，但是有可能把路程一算，反而更大。
因此，可以把
a[] ，即疲劳值中，前X 大中的最小值，即第X 大的那一家舍去，看看能不能通过走更远来换取更大的疲劳值总和。而从后面看，一定也会存在一个最大值，把这个最大值和前面
X-1 个疲劳值总和加起来，看看会不会比前面第一种的情况大。证明：只需舍去最小值来走更远，无需舍去更多数来走更远。
其实这也不是一个证明..
因为已经从大到小排序了，所以，如果舍去
2 个疲劳值，那么后面只会在加上两个更小的疲劳值，以及两个之间最大的距离并乘2，那么这样还不如只舍去一个。2个不行，那么2个以上更是不行了。
-
举例子了。
硬讲太累了，还是用一个例子吧。
//自动排序QAQ s[i]:1,3,4,5,11 a[i]:5,4,2,1,1若
X==1 ，直接取，那么值为:1×2+5=7 ,如果舍去最小的往后跑，值为:11×2+1=23 ，所以，最大值就为max(7,11)=11 。若
X==2 ，直接取，值为:3×2+5+4=15 ,把其中最小值舍去，也就是4 去掉，往后跑值为:11×2+1+5=28 ，那么最大值为max(15,28)=28 。若把次小疲劳值，即
5 ,也往后跑，那么值为11×2+1=24 ，可以发现，距离并未因此改变，仍为11 ，而位置移后，疲劳值只会减少，故只要移动最小疲劳值。那么，最后一个问题，酱紫复杂度是会炸掉的，
so 用
sum[] 记录疲劳前缀和，这样子加的时候方便。用
q[] 记录前i个距离最大值，这样子就不用找啦！用
h[] 记录往后跑时，应该选哪个，也就是后i个的最大值。这样子预处理，就可以实现
O(n) 啦QAQ ！ -
代码QAQ
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,sum[100010],q[100010],h[100010];//n 疲劳前缀和 前i个最大值 后i个最大值
struct node{
int s;//距离
int a;//疲劳
}v[100010];
bool cmp(node x,node y){return x.a>y.a;}
int main()
{ scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i].s);
for(int i=1;i<=n;i++)scanf("%d",&v[i].a);
sort(v+1,v+1+n,cmp);//按疲劳排序
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+v[i].a;
for(int i=1;i<=n;i++)q[i]=max(q[i-1],2*v[i].s);//前i个最大值
for(int i=n;i>=1;i--)h[i]=max(h[i+1],2*v[i].s+v[i].a);//后i个最大值
for(int i=1;i<=n;i++)printf("%d\n",max(sum[i]+q[i],sum[i-1]+h[i]));
return 0;
}