【基础练习】【贪心】tyvj1373 石子采集题解

以你之姓@ 2022-08-09 14:43 164阅读 0赞

此题改编自POJ1042

**P1373** 石子采集

时间: 1000ms / 空间: 131072KiB / Java类名: Main

## 背景 ##

某一天，小A正在备战noip（焦头烂额ing~）。他正对着屏幕发呆时，收到了陌生人发来的一封邮件，“恭喜您，获得了参加rp++一日游的机会，时间定在XXX日8:30，届时将会有很多OI界的神牛（sdzh~..），希望您能准时参加。”小A心里有些怀疑，但如此狂得rp的机会怎能轻易错过（大不了被虐），于是小A决定去参加……

## 描述 ##

小A一早就来到了活动地点，希望能见一见传说中的神牛，但发现到场的人里没有一个认识的。过了一会儿，他们每个人都收到了组织者的一封信。小A打开一看，只见上面写着：“你需要独自闯过四关，才能得到rp大礼包。现在，请你完成第一项任务。  
你需要在标号为1..n的山头上采彩色的石头，一开始是从1号山头出发，每次只能从一个山头移动到相邻的下一个山头，花费的时间将会给出。如果有多种可行的选择，你需要选标号尽可能靠前的山头。每个山头一开始可以采fi个彩色石头，采一次会花5分钟，每采一次能采的石头会减少di个（例如你在第j号山头采到fj个石头，下一次你还在该山头采，则这一次能采fj-dj个石头），你可以在任意一个山头停止。在给定的时间里，你需要采得尽可能多的石头。”

## 输入格式 ##

第一行为N（N<=1000)，下面有N行空格。  
接下来有多组数据（不多于500组），对于每一组：  
  一行为一个非负整数n(n<=25)；  
  一行为一个非负整数h(h<=16)，代表给定的时间（单位为小时）；  
  一行为n个非负整数fi；  
  一行为n个非负整数di；  
  一行为n-1个非负整数ti（ti表示从i号山头到i+1号所要花费的时间,单位为5分钟，0 < ti <=192；n为1时你需要忽略掉本行的数据）。  
 ……  
当n=0时输入结束。

## 输出格式 ##

对于每一组数据，输出如下：  
    第一行为n个实数（保留两位小数），代表小A在每个山头所花的时间,两两之间用一个空格隔开（单位：小时）；  
第二行一个数输出石头的最大数量；  
第三行输出一空行。

## 测试样例1 ##

### 输入 ###

> 0   
> 2   
> 1   
> 10 1   
> 2 5   
> 2   
> 0

### 输出 ###

> 0.75 0.08   
> 31   
>

## 备注 ##

第一个5分钟在山头1上，采到10个石子；    第二个5分钟在山头1上，采到10-2=8个石子；    ......      这样在山头1采到10+8+6+4+2=30个石子，用时25分钟；到山头2用时2\*5分钟；在山头2采到1个石子用时5分钟。    而题目中有要求，故剩余的60-25-2\*5-5=20分钟要在山头1呆着：即前(25+20)/60小时要在山头1；后5/60小时要在山头2；共采石子31个。

这道题目我并没有写，是比赛的第一题···然而样例被学长们捉弄的稀里糊涂···

在这里写一下简单的方法吧：

我们首先限定要走到哪个山头。显然只是单向走一次是最优的方案，往回走只会浪费时间。用best\[i\]表示确定走到第i个山头停止的最优解，这样对于每个best，用在路上的时间就确定了。之后我们求出剩下采石子的时间，贪心每次取最大即可。

这么说不好理解，举个例子

假设我们现在要求走到山头三德最优解，有十二个单位时间，从一到二和从二到三总共耗费三个时间，那么现在我们还有九个时间用来采石子。

现在三个山头的第一次可采石子分别为90，70，60，显然我们选择90，此时第一个山头的90变成了40，因此第二次选70，之后70变成50，于是我们第三次选60……以此类推。我们贪心选择的顺序是这样，实际采石子时，要先把第一个山头取完我们计算的再去取第二个山头的，等等。

这道题目更复杂，如果有多解，要尽量把时间放在第一个山头上。只需要在贪心时遇到多种可行解优先选择靠前的山头即可。

还有一个坑点，就是这道题目数据卡读入···什么意思，读入的时候读够了必要的就换行或者停止，后面会有多余数据···会一直让你读不完···