今天为大家讲一道贪心题目, 贪心类问题旨在找寻最优解.
题目描述
恶魔猎手尤迪安野心勃勃, 他背叛了暗夜精灵, 率领深藏在海底的娜迦族企图叛变. 守望者在与尤迪安的交锋中遭遇了围杀, 被困在一个荒芜的大岛上. 为了杀死守望者, 尤迪安开始对这个荒岛施咒, 这座岛很快就会沉下去. 到那时, 岛上的所有人都会遇难. 守望者的跑步速度为 17m/s, 以这样的速度是无法逃离荒岛的. 庆幸的是守望者拥有闪烁法术, 可在 1s 内移动 60m, 不过每次使用闪烁法术都会消耗魔法值 10 点. 守望者的魔法值恢复的速度为 4 点 / s, 只有处在原地休息状态时才能恢复.
现在已知守望者的魔法初值 M, 他所在的初始位置与岛的出口之间的距离 S, 岛沉没的时间 T. 你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛, 若不能逃出, 则输出守望者在剩下的时间内能走的最远距离. 注意: 守望者跑步, 闪烁或休息活动均以秒 (s) 为单位, 且每次活动的持续时间为整数秒. 距离的单位为米 (m).
输入
仅一行, 包括空格隔开的三个非负整数 M, S, T.
[限制]
30% 的数据满足: 1 <= T<= 10, 1 <= S <= 100
50% 的数据满足: 1 <= T<= 1000, 1 <= S <= 10000
100% 的数据满足: 1 <= T<= 300000, 0 <= M <= 1000, 1 <= S <= 108.
输出
包含两行:
第 1 行为字符串 "Yes" 或 "No"(区分大小写), 即守望者是否能逃离荒岛.
第 2 行包含一个整数. 第一行为 "Yes"(区分大小写) 时表示守望者逃离荒岛的最短时间; 第一行为 "No"(区分大小写) 时表示守望者能走的最远距离.
样例输入
36 255 10
样例输出 Yes
6
题解代码:
- #include
- using namespace std;
- int m,s,t,sum=0;
- int main(){
- scanf("%d%d%d",&m,&s,&t);
- for(int i=1;i<=t;i++){
- if(m>=10){
- sum+=60;
- m-=10;
- }
- else{
- int cost=(10-m)%4==0?(10-m)/4:(10-m)/4+1;// 计算需用的前进魔法值还需所耗时间
- if(cost<=t-i&&s-sum>=17*(cost+1)){
- m+=4;
- }
- else{
- sum+=17;
- }
- }
- if(sum>=s){
- printf("Yes\n%d\n",i);
- return 0;
- }
- }
- printf("No\n%d\n",sum);
- return 0;
- }
题解思路:
这道题对于很多算法刚刚入门的同学首先想到的可能是 bfs 求解, 但 bfs 问题求解范围过广, 内存消耗过大, 相比于贪心来讲, 时间复杂度要高的多,
贪心问题在于每一次筛选都筛选出最优解, 范围小, 时间复杂度也低得多.
对于这道题的思路:
这道题乍一看可能关系有点乱, 但仔细理一理思路弄清题意就不难理解了, 分为三种情况:
1. 守望者在 mp>=10 时释放技能直接走 60 米, 显然跑的最快, 所以 mp>=10 时比为最优解
2. 守望者在 mp<10 的情况, 有两种选择: 1) 继续跑, 1 秒跑 17m;2) 停下来休息, 恢复 4 点 mp 值.
对于这两种情况:
1) 当 mp 为 0 或 1 时, 恢复需要 3 秒 + 1 秒释放技能, 而以 17m/s 的速度前进 4 秒能走 68m, 而我们也需要保证剩余时间大于 4 秒, 当然向前前进更快.
2) 当 mp>1 时, 最多需要 2 秒恢复 + 1 秒释放技能, 单纯移动可以前进 51m
综上所述: 我们可以用一个 for 1 到 t 代表每秒末的状态,
1. 当 mp>=10 时, 释放技能走的最快.
2.mp<10 时, 我们就计算恢复所需的时间 t, 若而且距终点距离大于等于 17m/s 乘以 t, 即 (s-sum>=(cost+1)), 则恢复魔法,
mp+4; 当剩余时间 t-i>=cost 而且距离终点距离小于移动 17m/s 乘以 t, 则向前移动.
来源: http://www.bubuko.com/infodetail-3120251.html