技术宅社区 | Z站有爱，有技术，有你 ^_^)y»论坛 › 技术区 › 程序设计 › 技术问答 › 额。这是他们喜欢War3的人出的题。

查看: 824|回复: 13

额。这是他们喜欢War3的人出的题。

该用户从未签到

11 主题	37 好友	1万积分

第一章

积分: 18487

发表于 2013-4-19 10:54:33 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

Description：

恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，刀上的所有人都会遇难：守望者的跑步速度，为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。

Input：

输入仅一行，包括空格隔开的三个非负整数M，S，T。

Output：

输出包含两行:

第1行为字符串"Yes"或"No" (区分大小写)，即守望者是否能逃离荒岛。

第2行包含一个整数，第一行为"Yes" (区分大小写）时表示守望着逃离荒岛的最短时间

第一行为"No" (区分大小写) 时表示守望者能走的最远距离。

Sample Input：
39 200 4

Sample Output：
No
197

HINT：

30%的数据满足: 1 <= T<= 10， 1 <=S<= 100

50%的数据满足: 1 <= T <= 1000， 1 <= S <= 10000

100%的数据满足: 1 <= T <= 300000， 0 <= M<=1000 1 <=S <= 10^8

额。规律基本推出来了。基本就看你用完B还剩多少的MP。

但是。果断WA了。感觉做不来了。求思路就行。

签名被小宅喵吞掉了~~~~(>_<)~~~~

使用道具举报

繁尘、离梦

该用户从未签到

29 主题	54 好友	1万积分

懒人

尔等还不速速跪下~

积分: 11600

发表于 2013-4-19 11:06:12 | 显示全部楼层

我怎么感觉你是宁波大学的？我有个很好的朋友喜欢出这种题目给OJ

我先看看

点评

繁尘、离梦

好吧，这句当我没说发表于 2013-4-19 13:42

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

汝欠咱的一生

该用户从未签到

11 主题	37 好友	1万积分

第一章

积分: 18487

楼主| 发表于 2013-4-19 11:12:24 | 显示全部楼层

繁尘、离梦发表于 2013-4-19 11:06

登录/注册后可看大图

我怎么感觉你是宁波大学的？我有个很好的朋友喜欢出这种题目给OJ我先看看 ...

额。不是宁波的。

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

foodszhu

该用户从未签到

30 主题	127 好友	2万积分

技术宅认证程序员

重度中二患者

积分: 28325

发表于 2013-4-19 12:16:31 | 显示全部楼层

肯定是先耗干净蓝。。剩余蓝如果大于2,就多B一次。2s休息 + 1sB 60 > 17 * 3=51 。。剩1点蓝当他没有。。。休息5s + B2次2s = 7s，B出的距离是2 * 60 = 120m，而跑步只有7 * 17 = 119m，就是说当尽量选B着走。。。
就是根据剩余蓝和剩余距离尽量B。距离的阈值应该是60和120,根据剩余蓝量再考虑时间的阈值。。。应该差不多就是这样的策略。。
等上课我再仔细想想吧。。。先去吃饭

等死星人

回复支持反对

使用道具举报

繁尘、离梦

该用户从未签到

29 主题	54 好友	1万积分

懒人

尔等还不速速跪下~

积分: 11600

发表于 2013-4-19 12:56:56 | 显示全部楼层

吃完饭回来了，看了下，是这样的，这题目关键在于17这个数字和回蓝4点，你要做的是判断停或者跳。
看看停等蓝跳的平均速度。
如果0点蓝的时候，等3秒，12点蓝，第四秒跳，60米，剩余两点蓝，第5、6秒等，刚好10点蓝，第7秒跳，又剩下0点蓝。说明这是一个循环，非常巧妙。前四秒平均速度才15，后3秒20。
那么停等跳这个过程一共耗时 7秒，前进120米，想象成一个匀速过程，每秒跳跃，120/7=17.1的样子大概>17，这就是这个17的设置很合理的地方。恰好有木有，所以你要做的便是以下过程：
先把蓝跳光，这不用说吧，下面就是蓝不足的时候的取舍，根据上面理论，即使你一点蓝都没，选择等和跳依然比直接跑快。
当然快到终点前的7秒是有讲究的：如果在这前6秒能到终点了，直接跑的速度是17，选择直接跑最合适，如果你6秒过不去，不好意思，选择7秒这种循环方式可以平均速度大于17，比较快。
先睡个午觉，下午空的时候给你写下看。

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

繁尘、离梦

该用户从未签到

29 主题	54 好友	1万积分

懒人

尔等还不速速跪下~

积分: 11600

发表于 2013-4-19 13:40:28 | 显示全部楼层

[mw_shl_code=cpp,true]#include"iostream"
using namespace std;
int a[300001];
int main()
{
int m,s,t;
while (cin>>m>>s>>t)
{

int _t=t;

int _m=m;

a[0]=0;

for(int i=1;i<=t;i++)
{
if(_m>=10)
{
_m-=10;

a=a[i-1]+60;
}
else
{
a=a[i-1];

_m+=4;

}
}//最快的方式，能到则到了，不能到拉到

//当然有特殊情况，就是时间快到前的7秒，需要贪心处理最短时间和路程

int max_len=0;

max_len=a[t];

for(int i=1;i<=t;i++)
{
if(a<a[i-1]+17)a=a[i-1]+17;

if(a>=max_len)max_len=a;

if(a>=s)
{
cout<<"Yes"<<endl;cout<<i<<endl;

//cout<<"跳跃距离为"<<a<<endl;

break;
}

}

if(max_len<s){cout<<"No"<<endl;cout<<max_len<<endl;}

}

return 0;
}[/mw_shl_code]

点评

繁尘、离梦

一开始想优化最后段，贪心过程，把时间缩到最后的7秒钟再贪心就可以了，好几天没写文章了，写文章去了，你自己想吧哈哈，变量定义了都没用哈哈发表于 2013-4-19 13:44

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

汝欠咱的一生

该用户从未签到

11 主题	37 好友	1万积分

第一章

积分: 18487

楼主| 发表于 2013-4-19 15:57:15 | 显示全部楼层

繁尘、离梦发表于 2013-4-19 12:56

登录/注册后可看大图

吃完饭回来了，看了下，是这样的，这题目关键在于17这个数字和回蓝4点，你要做的是判断停或者跳。
看看停等 ...

表示最开始拿笔画了半天，才了解了它卡的那个位置。

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

繁尘、离梦

该用户从未签到

29 主题	54 好友	1万积分

懒人

尔等还不速速跪下~

积分: 11600

发表于 2013-4-19 16:40:03 | 显示全部楼层

汝欠咱的一生发表于 2013-4-19 15:57

登录/注册后可看大图

表示最开始拿笔画了半天，才了解了它卡的那个位置。

贪心的问题，如何去模拟是关键。

加油吧

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

jains521

该用户从未签到

14 主题	22 好友	7919 积分

序章

积分: 7919

发表于 2013-4-21 13:08:22 | 显示全部楼层

本帖最后由 jains521 于 2013-4-21 13:11 编辑

s=vt
所以有2个路程有2个速度和2个时间.
t跑=s跑/v跑
t闪=s闪/60+1+2.5
t总=t跑+t闪
s总=s闪+s跑
当然为了安全起见, 需要加一个判断, 假设在没蓝的情况下, s剩<=60 . t剩的时间需要3.5秒 3.5*17=59.5米
总结一下, 有蓝的情况只管闪, 没蓝就按剩余量来.
当然最重要的是时间基准是1秒, 是
t闪= 3+1=60
t跑=4*17=68
需要合理利用的是那0.5秒时间.

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

渣渣小夏喵

该用户从未签到

0 主题	4 好友	1837 积分

Continue

积分: 1837

发表于 2013-4-24 09:01:45 来自手机 | 显示全部楼层

这是虾米。。触发编辑器么。。

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

Mr_Alex

签到天数: 3 天

连续签到: 1 天

[LV.2]偶尔看看I

41 主题	60 好友	2万积分

第一章

守望者

积分: 21763

发表于 2013-4-24 13:50:54 | 显示全部楼层

随手谢了个，经测试没发现什么问题。用的JAVA写的

[mw_shl_code=java,true]
/**
   *
   * @param M 魔法值
   * @param S 逃离距离
   * @param T 时间
   */
public static void warThree(int M,int S,int T){

int shanNum = 0 ;
int paoTime = 0 ;
int xiuTime = 0 ;
boolean tao = false ;
int taoS = 0 ;
int taoT = 0 ;

shanNum = M/10 ; //刚开始尽可能多的用闪技能
if(shanNum > 0){
if(T <= shanNum) //得到可以用闪的次数
shanNum = T ;
if(shanNum * 60 >= S && shanNum >=T) { //如果只用闪就可以逃离
tao = true ;
taoT = (int) Math.ceil(S/60.0) ;
S=0 ;
}else{
taoS += 60*shanNum ;
S = S - 60*shanNum ;
T = T - shanNum ;
M = M%10 ;
taoT += shanNum ;
}
}
//魔法值小于10的时候,如果恢复魔法了使用魔法的时间和小于剩余时间值，则休息恢复魔法，否则就采用跑的手段
while (S>0 && true) {
if (Math.ceil((10 - M) / 4.0) + 1 <= T) {
xiuTime += (int) Math.ceil((10 - M) / 4.0);
shanNum++;
S = S - 60;
T = T - (int) Math.ceil((10 - M) / 4.0) - 1;
taoT += (int) Math.ceil((10 - M) / 4.0) + 1 ;
taoS += 60 ;
if(S <= 0 ) {
tao = true ;
break;
}
}else{
if(17*T >= S){ //采用跑可以逃离
paoTime = (int) Math.ceil(S/17.0);
S = 0 ;
taoT += paoTime;
tao = true ;
break ;
}else{//无法逃离
paoTime = T ;
S = S - 17*T ;
taoT += T ;
taoS += 17*T ;
T=0;
break;
}

}
}

if(tao) {
System.out.println("YES");
System.out.println(taoT);
}
else {
System.out.println("NO");
System.out.println(taoS);

}

}[/mw_shl_code]

如果有来生，要做一棵树，站成永恒，没有悲欢的姿势。一半在土里安详，一半在风里飞扬，一半洒落阴凉，一半沐浴阳光，非常沉默非常骄傲，从不依靠从不寻找。

回复支持反对

使用道具举报