描述:https://www.luogu.com.cn/problem/P2672
阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si?米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。
阿明每走1米就会积累1点疲劳值，向第ii家住户推销产品会积累Ai?点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。
#include <bits/stdc++.h> using namespace std; struct p{ int s,v; }a[100009]; int sumn[100009],h[100009],qm[100009]; bool com(p a,p b){ return a.v>b.v; } int main() { int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i].s; for(int i=1;i<=n;i++) cin>>a[i].v; sort(a+1,a+1+n,com); for(int i=1;i<=n;i++) sumn[i]=sumn[i-1]+a[i].v,qm[i]=max(qm[i-1],a[i].s);//前x项距离的最大值 for(int i=n;i>=1;i--) h[i]=max(h[i+1],2*a[i].s+a[i].v); for(int i=1;i<=n;i++) cout<<max(sumn[i]+qm[i]*2,sumn[i-1]+h[i])<<endl; }
原文：https://www.cnblogs.com/iss-ue/p/12536530.html