正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2672

---

題目大意

每家住戶有一個位置$l_i$，推銷會產(chǎn)生的疲勞值$a_i$，向X家住戶推銷產(chǎn)品，對于每個X，要求使
$$\sum _{i=1}^X{a}_{x_i}+2?max\{l_{x_i}\}$$
最大($x_i$表示選擇的住戶)

---

解題思路

首先顯然發(fā)現(xiàn)只有兩種答案的可能，那就是取$X$個$a_i$最大的，或者取$X?1$個最大的$a_i$和一個$x_i?2+a_i$最大的
所以答案就是，然后再將兩個答案比較。

---

code

#include<cstdio> #include<algorithm> #define N 100010 struct node{int p,l; }a[N]; int n,s[N],h[N],ml[N]; using namespace std; bool cmp(node x,node y) {return x.p>y.p;} int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i].l);for(int i=1;i<=n;i++)scanf("%d",&a[i].p);sort(a+1,a+1+n,cmp);//排序for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i].p,ml[i]=max(ml[i-1],a[i].l);//前i個的和and前i個最大的lfor(int i=n;i>=1;i--)h[i]=max(h[i+1],a[i].l*2+a[i].p);//后到第i個最大的l[i]*2+a[i]for(int i=1;i<=n;i++)printf("%d\n",max(s[i]+ml[i]*2,s[i-1]+h[i]));//輸出 }

總結(jié)

以上是生活随笔為你收集整理的P2672-推销员【贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。