题解 P1095 【守望者的逃离】
wjyyy
2018-02-23 21:16:18
题目标签是 贪心+DP，但是实际上我是贪心+模拟出来结果的（不知道是不是数据弱了，欢迎$dalao$们**$hack$**）
### **题解中有关贪心的内容我都会把它加粗变♂大**
定义一下
$s$是距离,
$v=s/t$是单位时间的速度，使用闪现的时候是$v=60/1=60$，正常行走的时候是$v=17/1=17$。积攒一个闪现加上释放：最好情况是魔法在$10$或以上，$v=60/1=60$；最坏情况是没有魔法：积攒和释放共需要$4$秒，平均速度$v$就是$v=60/4=15$。
### **首先，有魔法（$=10$）的时候，一定要用闪现，这时速度是最快的，$v=60$，这里是贪心的一个点，尽可能让速度快。**
当魔法耗尽时（$<10$），有两种情况：
1.剩余$0~1$，补充$3$次魔法可以用闪现，平均速度是$v=60/4=15$，能走$60m$，耗费$4$秒，但比行走慢；补充$5$次魔法可以用两次闪现，平均速度是$v=120/7=17.14$，能走$120m$，耗费$7$秒，比行走快。
2.剩余$2~9$，补充$1~2$次魔法后可以用一次闪现，平均速度分别是$v=60/2=30,v=60/3=20$，耗费$2$秒和$3$秒，都比行走快。
### **因此，在以上两种情况中，离终点较远的情况下，闪现是比行走要快的，同理是贪心的思想。**
除此之外，我们还要特判快到终点（定为$s<68$）的情况，利用表格来说明
| 剩余魔法 | 0~1 | 2~5 | 6~9 |效果|
| -----------: | -----------: | -----------: | -----------: |
| 使用1次闪现 |耗时4s|耗时3s|耗时2s|距离60m|
| 不使用闪现 |耗时1s|耗时1s|耗时1s|距离17m||
列出下一次闪现需要几秒恢复：$f(m)=(10-m-1)/4+2$（算上使用的$1s$）向下取整
所以$f(0)=4,s=60$而$4s$可以走（正常行走）$68m$
$f(1)=4,$ $4s$可以走$68m$
因此在$t>=4$且$s<68$时正常行走就可以出去
$f(2)=3,$ $4s$可以走$51m $
$f(3)=3,$ $f(4)=3,$ $f(5)=3,$ $f(6)=2,$
$f(7)=2,$ $f(8)=2,$ $f(9)=2$
均同理
以上判断方程为($sum$是最终结果,$m$因为在$while$循环中耗尽,$m<10$)
$if((9-m)/4+2>=((s-1)/17+1))$
```cpp
if(m<10&&t>=(s-1)/17+1&&(9-m)/4+2>=((s-1)/17+1))
{
t-=(s-1)/17+1;
s=0;
break;
}
```
$(9-m)/4+2$ 是使用闪现所耗费的总时间
$((s-1)/17+1))$是行走耗费的总时间
行走耗时更少的话当然是选择行走了，因为可以拆成更少的时间段来进行，**举个栗子**
| 剩余魔法 | $Δm$ |$1$|
| -----------: | -----------: |
| 剩余距离 | $Δs$ |$18$|
| 剩余时间 | $Δt$ |$3$|
可以看出，当$Δs=18$时，只需2s就可以直接走出去了，而补充魔法用闪现需要$4s$
### 这里当然是选择贪$2s$了，这些思想在代码里都有体现。
# Code：
```cpp
#include<cstdio>
int main()
{
int m,s,t,S,T;
scanf("%d%d%d",&m,&s,&t);
S=s;//S,T用来存初始值，方便最后一步算出结果
T=t;
while(s>0&&t>0)//循环的边界，也是最终判断的依据
{
if(m>=10)//当m>=10时，用闪现是最快的，没有之一，贪心思想
{
m-=10;
s-=60;
t--;
}
else if(m<10&&((9-m)/4+1)<t)//判断是休息还是直接开溜
{
if((9-m)/4+2>=((s-1)/17+1))//当能直接开溜的时候，贪心贪最小的
{
t-=(s-1)/17+1;
s=0;
break;
}
m+=4;
t--;
}
else//不特判的情况，也不休息，直接正常行走，比如当t较小的时候
{
s-=17;
t--;
}
}
if(s<=0)
printf("Yes\n%d\n",T-t);
else if(t<=0)
printf("No\n%d\n",S-s);
return 0;
}
```