NOIP2015 普及組第四題 推銷員

瘋狂的函數 2022-01-07 20:34:55 阅读数:88

noip2015 noip 普及 第四

題目描述

阿明是一名推銷員,他奉命到螺絲街推銷他們公司的產品。螺絲街是一條死胡同,出口與入口是同一個,街道的一側是圍牆,另一側是住戶。螺絲街一共有 N 家住戶,第 i 家住戶到入口的距離為 SiS_iSi 米。由於同一棟房子裏可以有多家住戶,所以可能有多家住戶與入口的距離相等。阿明會從入口進入,依次向螺絲街的 X 家住戶推銷產品,然後再原路走出去。 阿明每走 1 米就會積累 1 點疲勞值,向第 i 家住戶推銷產品會積累 AiA_iAi 點疲勞值。阿明是工作狂,他想知道,對於不同的 X,**在不走多餘的路的前提下**,他最多可以積累多少點疲勞值。

輸入

第一行有一個正整數 N,錶示螺絲街住戶的數量。

接下來的一行有 N 個正整數,其中第 i 個整數 SiS_iSi 錶示第 i 家住戶到入口的距離。數據保證 S1S_1S1≤S2S_2S2≤…≤SnS_nSn<108108108。

接下來的一行有 N 個正整數,其中第 i 個整數 AiA_iAi 錶示向第 i 戶住戶推銷產品會積累的疲勞值。數據保證 AiA_iAi<103103103。

輸出

輸出 N 行,每行一個正整數,第 i 行整數錶示當 X=i 時,阿明最多積累的疲勞值。

樣例輸入

樣例輸入1
5
1 2 3 4 5
1 2 3 4 5
樣例輸入2
5
1 2 2 4 5
5 4 3 4 1

樣例輸出

樣例輸出1
15
19
22
24
25
樣例輸出2
12
17
21
24
27

提示

對於 20%的數據,1≤N≤20;

對於 40%的數據,1≤N≤100;

對於 60%的數據,1≤N≤1000;

對於 100%的數據,1≤N≤100000。

【輸入輸出樣例 1 說明】

X=1: 向住戶 5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值為 5,總疲勞值為 15。

X=2: 向住戶 4、5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值為 4+5,總疲勞 值為 5+5+4+5=19。

X=3: 向住戶 3、4、5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值 3+4+5,總疲 勞值為 5+5+3+4+5=22。

X=4: 向住戶 2、3、4、5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值 2+3+4+5, 總疲勞值 5+5+2+3+4+5=24。

X=5: 向住戶 1、2、3、4、5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值 1+2+3+4+5, 總疲勞值 5+5+1+2+3+4+5=25。

【輸入輸出樣例 2 說明】

X=1:向住戶 4 推銷,往返走路的疲勞值為 4+4,推銷的疲勞值為 4,總疲勞值 4+4+4=12。 X=2:向住戶 1、4 推銷,往返走路的疲勞值為 4+4,推銷的疲勞值為 5+4,總疲勞值4+4+5+4=17。

X=3:向住戶 1、2、4 推銷,往返走路的疲勞值為 4+4,推銷的疲勞值為 5+4+4,總疲勞值 4+4+5+4+4=21。

X=4:向住戶 1、2、3、4 推銷,往返走路的疲勞值為 4+4,推銷的疲勞值為 5+4+3+4, 總疲勞值 4+4+5+4+3+4=24。或者向住戶 1、2、4、5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值為 5+4+4+1,總疲勞值 5+5+5+4+4+1=24。

X=5:向住戶 1、2、3、4、5 推銷,往返走路的疲勞值為 5+5,推銷的疲勞值為 5+4+3+4+1, 總疲勞值 5+5+5+4+3+4+1=27。

程序實現

#include<bits/stdc++.h>
struct pl{
int s,val;
}a[100005];
int maxx,j,k,ans;
using namespace std;
bool cmp(pl x,pl y)
{
return x.val>y.val;
}
int main()
{
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].s);
}
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].val);
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++)
if (2*a[i].s+a[i].val>maxx)
{
maxx=2*a[i].s+a[i].val;
j=k=i;
}
ans+=maxx;
printf("%d\n",ans);
for (int i=1;i<=n;i++)
{
if (i==k)
{
continue;
}
if (a[j].s<a[i].s)
{
ans=ans-2*a[j].s+2*a[i].s+a[i].val;
j=i;
printf("%d\n",ans);
}
else
{
ans+=a[i].val;
printf("%d\n",ans);
}
}
return 0;
}

版权声明:本文为[瘋狂的函數]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072034548349.html