注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

信息学夏令营的考试...(1) (2009-03-15 20:57:58)  

2014-09-02 10:29:56|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
标签: 

杂谈

测试题...提高二..

一、迟到的午餐 (food.cpp/c/pas)

 

时间限制: 1000MS        空间限制: 65536K

描述

在夏令营的食堂领午饭是一件非常让人抓狂的事情——人数过多导致每次都需要排很久的时间才能够领到饭。

tHeem_Lody坚持认为这是由于厨房工作人员盛饭效率过低导致。

经过观察,他把盛饭的过程抽象成一个模型:n个等待盛饭的OIers站成一列,每个人都有一个身高hi。每次工作人员可以从任一个OIer开始盛饭,然后为了节省力气,他会依次按照站的顺序向后给身高不大于上一个盛饭对象的身高的OIer盛饭,为了节约,每个OIer只盛饭一次。

即,如果一次盛饭的对象身高集合为a,那么a必定满足a1>=a2>=a3>=a4……

很显然,在要给所有OIers盛饭的前提下,每次盛饭选择不同的第一个盛饭的对象所需要的盛饭次数是不同的。

你能够帮助tHeem_Lody求出最少需要的盛饭次数,使得所有OIers都领到自己期盼已久的午餐吗?

 

输入 (food.in)

第一行,一个数 n ,等待排队的OIers的人数

第二行,n个空格隔开的整数,第i个数表示第i个OIer的身高hi

(对于40%的数据,n<=1000

对于60%的数据,n<=5000

对于100%的数据,n<=100000,-2^31<h<2^31)

 

输出 (food.out)

一行,输出最少盛饭次数

 

样例输入

5

1 5 4 6 2

 

样例输出

3

 

样例说明

       3次盛饭对象分别为:①1 ②5 => 4 >=2 ③6

由于第1个OIer的身高为1,后面没有比他再矮的OIer,所以这一次盛饭对象只有他一个人,第二次盛饭给身高为5的OIer盛饭,然后依次给其后面的,比起身高低的身高为4的OIer盛饭,接着再给身高为2的OIer盛饭。

       显然也存在其他方案,比如可以①1 ②5 => 4 ③6 >=2

 

题解:见导弹拦截一题第二问...

 

 

二、背影 (beauty.cpp/c/pas)

 

时间限制: 1000MS        空间限制: 65536K

描述

某日,tHeem_Lody,Gnocuil,SubRaY和Jason911在去机房的路上,发现了一个mm的美丽的背影。但单纯从背面是很难以判断一个mm的长相的,于是四人决定赶上前去一睹庐山真面目。

将四人与mm的地点抽象成一个坐标轴,四人的位置为st,mm的位置为en。

为了增加挑战性,和照顾跑不快的Jason911,SubRaY提议用走和飞的方式追赶,设当前坐标为i,则每一步有如下三种方式:

1.      进一步,即到达i+1

2.      退一步,即到达i-1

3.      飞一下,即到达i*2

 

假设每个人进行任一种方式耗时是一样的,所以谁用的步数少,谁就能最先赶上mm。

为了降低难度,假设mm的位置是不变的,你能够帮助tHeem_Lody求出最少需要多少步,才能准确到达mm所在的位置吗?

 

输入 (beauty.in)

一行,两个空格隔开的整数st,en

对于50%的数据 (0<=st,en<=10,000)

对于100%的数据 (0<=st,en<=100,000),不保证st<en

 

输出 (beauty.out)

一行,表示最少需要的步数

 

样例输入

  17

 

样例输出

4

 

样例说明

tHeem_Lody站在5,mm位置是17

1步,退一步,位置为4

2步,飞一下,位置为8

3步,飞一下,位置为16

4步,进一步,位置为17

题解:bfs或动规...

 

 

  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017