*Part2.5 P2672 推销员 【贪心、前缀和】

原题链接：P2672 [NOIP2015 普及组] 推销员 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

螺丝街一共有NN家住户，第ii家住户到入口的距离为S_iSi?米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的XX家住户推销产品，然后再原路走出去。

阿明每走11米就会积累11点疲劳值，向第ii家住户推销产品会积累A_iAi?点疲劳值。阿明是工作狂，他想知道，对于不同的XX，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

思路：前缀和优化

评价：

 1 #include
 2 using namespace std;
 3 //#define mod 1000000007
 4 typedef long long ll;
 5 int sum[100010], q[100010], h[100010]; //n 疲劳前缀和 前i个最大值 后i个最大值
 6 struct node
 7 {
 8     int s;//距离
 9     int v;//疲劳
10 } a[100010];
11 bool cmp(struct node e1,struct node e2) {return e1.v > e2.v;}
12 int main()
13 {   
14     int n;
15     scanf("%d", &n);
16     for(int i=1;i<=n;i++) scanf("%d",&a[i].s);
17     for(int i=1;i<=n;i++) scanf("%d",&a[i].v);
18     sort(a+1,a+1+n,cmp);
19     for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].v;
20     for(int i=1;i<=n;i++) q[i]=max(q[i-1],2*a[i].s);
21     for(int i=n;i>=1;i--) h[i]=max(h[i+1],2*a[i].s+a[i].v);
22     for(int i=1;i<=n;i++) printf("%d\n",max(sum[i]+q[i],sum[i-1]+h[i]));
23     return 0;
24 }