team2012-E1-mysol-0008

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

给出 n 个城市，以及初始的金钱 x0 和攻击力 y0
在每个城市，可以花费 a[i] 单位的钱提升 1 单位的攻击力，提升量可以是小数
在离开这个城市前，将收到 b[i] * y[i] 的收益，其中 y[i] 是当前攻击力

这是一道很厉害的贪心题，比赛当时我没有找到正确的解法
实际上，这题倒着想就容易多了，做法如下：
1. 很明显，如果决定在一个地方购买攻击力，那么一定是将钱全部花完
2. 处理到第 i 天，假设之前在任何日子里 (j > i) 都不打算买攻击力
   那么在第 i 天是否购买攻击力，取决于 a[i] 是否小于 sum(b[i] .. b[n])
3. 处理到第 i 天，假设之前已经决定好在最近的第 j 天购买攻击力 (j > i)
   如果在第 i 天买了攻击力，然后再在第 j 天买，最终得到的收益比起
   仅仅在第 j 天购买攻击力更多，那么就在第 i 天也购买攻击力

意识流证明如下：
1. 在序列的头部加入一个元素，能够使值更优，显然则加入
2. 在序列的头部加入一个元素，不会使值更优，那么有两种决策：
   a. 不加入这个元素
   b. 删除序列中某些元素再加入这个元素
      因为是倒着处理的，并且已有的元素都能提升总收益
      所以删除任何元素只会降低收益，因此在 (b) 决策内的
      最佳做法是只加入不删除，但这种做法比 (a) 会更差
      综上，只会选择【不加入这个元素】的决策

// By 猛犸也钻地 @ 2012.07.19 */
}}}

{{{
#include <cstdio>
using namespace std;

double a[100000],b[100000],s[100001],x,y;
int flag[100000],n;

int main(){
    while(scanf("%d%lf%lf",&n,&x,&y)==3){
        for(int i=0;i<n;i++) scanf("%lf%lf",a+i,b+i);
        s[n]=a[n]=0;
        for(int i=n-1,j=n;~i;i--){
            s[i]=b[i]+s[i+1];
            if(s[i]-a[i]<=s[j]-a[j]) flag[i]=0; else flag[j=i]=1;
        }
        for(int i=0;i<n;i++){
            if(flag[i]==1) y+=x/a[i],x=0;
            x+=b[i]*y;
        }
        printf("%.2f\n",x);
    }
}
}}}

/* 解题报告 //
给出 n 个城市，以及初始的金钱 x0 和攻击力 y0
在每个城市，可以花费 a[i] 单位的钱提升 1 单位的攻击力，提升量可以是小数
在离开这个城市前，将收到 b[i] * y[i] 的收益，其中 y[i] 是当前攻击力
这是一道很厉害的贪心题，比赛当时我没有找到正确的解法
实际上，这题倒着想就容易多了，做法如下：
1. 很明显，如果决定在一个地方购买攻击力，那么一定是将钱全部花完
2. 处理到第 i 天，假设之前在任何日子里 (j > i) 都不打算买攻击力
   那么在第 i 天是否购买攻击力，取决于 a[i] 是否小于 sum(b[i] .. b[n])
3. 处理到第 i 天，假设之前已经决定好在最近的第 j 天购买攻击力 (j > i)
   如果在第 i 天买了攻击力，然后再在第 j 天买，最终得到的收益比起
   仅仅在第 j 天购买攻击力更多，那么就在第 i 天也购买攻击力
意识流证明如下：
1. 在序列的头部加入一个元素，能够使值更优，显然则加入
2. 在序列的头部加入一个元素，不会使值更优，那么有两种决策：
   a. 不加入这个元素
   b. 删除序列中某些元素再加入这个元素
      因为是倒着处理的，并且已有的元素都能提升总收益
      所以删除任何元素只会降低收益，因此在 (b) 决策内的
      最佳做法是只加入不删除，但这种做法比 (a) 会更差
      综上，只会选择【不加入这个元素】的决策
// By 猛犸也钻地 @ 2012.07.19 */

#include <cstdio>
using namespace std;
double a[100000],b[100000],s[100001],x,y;
int flag[100000],n;
int main(){
    while(scanf("%d%lf%lf",&n,&x,&y)==3){
        for(int i=0;i<n;i++) scanf("%lf%lf",a+i,b+i);
        s[n]=a[n]=0;
        for(int i=n-1,j=n;~i;i--){
            s[i]=b[i]+s[i+1];
            if(s[i]-a[i]<=s[j]-a[j]) flag[i]=0; else flag[j=i]=1;
        }
        for(int i=0;i<n;i++){
            if(flag[i]==1) y+=x/a[i],x=0;
            x+=b[i]*y;
        }
        printf("%.2f\n",x);
    }
}