題目描述?Description

阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產(chǎn)品。螺絲街是一條死胡同，出口與入口是同一個(gè)，街道的一側(cè)是圍墻，另一側(cè)是住戶。螺絲街一共有N家住戶，第i家住戶到入口的距離為Si米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的距離相等。阿明會(huì)從入口進(jìn)入，依次向螺絲街的X家住戶推銷產(chǎn)品，然后再原路走出去。阿明每走1米就會(huì)積累1點(diǎn)疲勞值，向第i家住戶推銷產(chǎn)品會(huì)積累Ai點(diǎn)疲勞值。阿明是工作狂，他想知道，對于不同的X，在不走多余的路的前提下，他最多可以積累多少點(diǎn)疲勞值。

輸入描述?Input Description

第一行有一個(gè)正整數(shù)N，表示螺絲街住戶的數(shù)量。
接下來的一行有N個(gè)正整數(shù)，其中第i個(gè)整數(shù)Si表示第i家住戶到入口的距離。數(shù)據(jù)保證S1≤S2≤…≤Sn<10^8。
接下來的一行有N個(gè)正整數(shù)，其中第i個(gè)整數(shù)Ai表示向第i戶住戶推銷產(chǎn)品會(huì)積累的疲勞值。數(shù)據(jù)保證Ai<10^3。

輸出描述?Output Description

輸出N行，每行一個(gè)正整數(shù)，第i行整數(shù)表示當(dāng)X=i時(shí)，阿明最多積累的疲勞值。

樣例輸入?Sample Input

【樣例1】
5
1?2?3?4?5
1?2?3?4?5

【樣例2】
5
1?2?2?4?5
5?4?3?4?1

樣例輸出?Sample Output

【樣例1】
15
19
22
24
25

【樣例2】
12
17
21
24
27

數(shù)據(jù)范圍及提示?Data Size & Hint

1≤N≤100000
注：請用?scanf?輸入。

/*剛開始想了一個(gè)貪心思路，不知道對不對，然而真的就對了，只不過是O(n^2)的，TLE，然后用優(yōu)先隊(duì)列優(yōu)化就過了。貪心思路首先我們明確，找前i個(gè)住戶一定是在i-1的基礎(chǔ)上找的，具體方法是記錄當(dāng)前我們最遠(yuǎn)找到的村莊位置now，因?yàn)楫?dāng)你往回找和往前找時(shí)走的路程是不同的，對于now來說，我們有兩種決策，一種是向上找，一種是向下找，找到最大值加入ans，這樣是O(n^2)的方法。然而我們發(fā)現(xiàn)向上找的部分會(huì)隨now的變大而逐漸不浪費(fèi)時(shí)間，向下找的部分則會(huì)重復(fù)找很多次，所以我們搞一個(gè)優(yōu)先隊(duì)列，再記錄一個(gè)當(dāng)前最遠(yuǎn)的入隊(duì)元素位置from，每次當(dāng)我們更新now時(shí)，就把from+1到now內(nèi)的元素放入優(yōu)先隊(duì)列，這樣我們在下一次向下找的時(shí)候就不用再循環(huán)一遍，而是直接從優(yōu)先隊(duì)列中取頭元素就好了。 */ #include<cstdio> #include<iostream> #include<queue> #include<algorithm> #define M 100010 using namespace std; int n,ans; struct node {int v,pos;bool operator< (node x)const{return v<x.v;} };node a[M],b; priority_queue<node> q; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i].pos);for(int i=1;i<=n;i++)scanf("%d",&a[i].v);b.v=0;b.pos=0;q.push(b);int now=0,from;for(int i=1;i<=n;i++){b=q.top();int mx=b.v,p=0;for(int j=now+1;j<=n;j++)if((a[j].pos-a[now].pos)*2+a[j].v>mx){mx=(a[j].pos-a[now].pos)*2+a[j].v;p=j;}if(p){b.pos=p;b.v=mx;from=now;now=p;q.push(b);for(int j=from+1;j<now;j++)q.push(a[j]);}node b=q.top();ans+=b.v;q.pop();printf("%d\n",ans);}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/harden/p/5811386.html

總結(jié)

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

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