题解：P2672 [NOIP 2015 普及组] 推销员

题目传送门

是道很好的题
代码实现难度很低很低
但是基础的思维量还是能保证的
但是建议调绿
十五分钟就写完了
关键词：贪心、前后缀

---

先简化题意

给出两个数列 \(疲惫_i\) 、 \(路程_i\)
他们的编号构成集合 \(S\)

\[\forall k \in [1,N]\\ card(K) = k\ \ \&\&\ \ K \in S\\ f(k) = \sum_{i \in K} 疲惫_i + max_{i \in K}\{ 路程_i \} \]

简化思考

不难发现，若选出K个数，我们不妨将 \(疲惫_i\) 降序
直接把他的前缀和求出来，然后再处理他们之中最大的 \(路程_i\)
这是 \(f(k)\) 的第一种求法
然后我们又发现，我们此时去掉这时的 \(K\) 中 \(疲惫_i\) 最小的
然后拿后面 \(路程_i\) \(\ge\) \(max_{i \in K}\{ 路程_i \}\) 的那些点去更新
其实上面这句话就等于，求出 按路程升序排序时 \(2\times 路程_i + 疲惫_i\) 的后缀和就好了
$\ $
好贪兄弟好贪

---

我们上CODE

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int n,ans[N],now,suf[N],nid,pre[N];struct node{int c,x,id;
}a[N];bool cmp(node a,node b){return a.c>b.c;
}main(void){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++)cin>>a[i].x;for(int i=1;i<=n;i++)cin>>a[i].c,a[i].id=i;for(int i=n;i>=1;i--)suf[i]=max(suf[i+1],2*a[i].x+a[i].c);//默认按照距离升序 ,处理贡献后缀 sort(a+1,a+1+n,cmp);//换成权值降序 for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i].c;//处理前缀权值 for(int i=1;i<=n;i++){if(a[i].x>now)now=a[i].x,nid=a[i].id;cout<<max(pre[i]+2*now,pre[i-1]+suf[nid+1])<<endl;}
}