猫史档案馆

原题链接：http://acm.ocrosoft.com/problem.php?cid=2035&pid=4

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条喵胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 N 家住户，第 ii 家住户到入口的距离为 Si 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 X 家住户推销产品，然后再原路走出去。

阿明每走 1 米就会积累 1 点疲劳值，向第 i 家住户推销产品会积累 Ai 点疲劳值。阿明是工作狂，他想知道，对于不同的 X ，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

输入 输入格式：

第一行有一个正整数 N ，表示螺丝街住户的数量。

接下来的一行有 N 个正整数，其中第 i个整数 Si 表示第 i 家住户到入口的距离。数据保证 S_1≤S_2≤…≤S_n<10^8

接下来的一行有 NN 个正整数，其中第 ii 个整数 A_iAi 表示向第 ii 户住户推销产品会积累的疲劳值。数据保证 Ai<1000 。

输出 输出 N 行，每行一个正整数，第i行整数表示当 X=i 时，阿明最多积累的疲劳值。 样例输入

5 1 2 3 4 5 1 2 3 4 5

样例输出

15 19 22 24 25

说明

【输入输出样例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

 

【数据说明】

对于 20% 的数据， 1≤N≤20；

对于 40% 的数据， 1≤N≤100 ；

对于 60% 的数据， 1≤N≤1000 ；

对于 100% 的数据， 1≤N≤100000

 

符合贪心策略。

//思路就是一个一个的累加疲劳值前x的人，分情况讨论怎么加疲劳值 
#include<bits/stdc++.h>
using namespace std;
struct tui{
    int s,val;
}a[100005];//s表示距离，val表示疲劳值 
bool cmp(tui a,tui b){
    return a.val>b.val;
}
int main(){
int i,j,k,ans=0,maxx=0,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i].s);
    for(i=0;i<n;i++)scanf("%d",&a[i].val);
    sort(a,a+n,cmp); 
    for(i=0;i<n;i++){
        if(2*a[i].s+a[i].val>maxx){
            j=k=i;//j,k都等于i 
            maxx=2*a[i].s+a[i].val;
        }
}//个是找出x=1的答案。去要走回来，2*a[i].s  加上a[i].val
   ans+=maxx;
   printf("%d\n",ans);//输出第一个答案
   for(i=0;i<n;i++){
       if(i==k)continue;//刚刚已经用k记录了最大疲劳值所以遇到k就跳过
       if(a[j].s<a[i].s)//如果某一个答案距离比k的更大，那我们就减去k的距离加上现在i的距离，因为每次找疲劳值最大，所以当经过i，就一定会k。不重复走要这样做
        {
            ans=ans-2*a[j].s+2*a[i].s;
            j=i;//修改当前最远的答案距离
            ans+=a[i].val;
            printf("%d\n",ans);
        }
        else{//因为i在j之前，所以经过j就一定会经过i
            ans+=a[i].val;
            printf("%d\n",ans);
        }
   }
   return 0;
}

下面这是详细解析，

核心部位：

for(i=0;i<n;i++){
       if(i==k)continue;//刚刚已经用k记录了最大疲劳值所以遇到k就跳过
       if(a[j].s<a[i].s)//如果某一个答案距离比k的更大，那我们就减去k的距离加上现在i的距离，因为每次找疲劳值最大，所以当经过i，就一定会k。不重复走要这样做
        {
            ans=ans-2*a[j].s+2*a[i].s;
            j=i;//修改当前最远的答案距离
            ans+=a[i].val;
            printf("%d\n",ans);
        }
        else{//因为i在j之前，所以经过j就一定会经过i
            ans+=a[i].val;
            printf("%d\n",ans);
        }
   }