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

xiaochen7777的博客

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐
 
 

信息学夏令营的考试...(1) (2009-03-15 21:01:13)  

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

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

杂谈

三、排队 (csort.cpp/c/pas)

 

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

 

描述

到了参加夏令营的地方,sd的Oiers们要按照身高从低到高排成一队去报名,老师把这个任务交给了tHeem_Lody。为了为难tHeem_Lody,老师把问题复杂化了:即每次只能移动交换两个人的位置。

已知有N(≤ N ≤ 10,000)个Oiers(sd今年好多人……)站成一列(高度不一定递增),而且每一个Oiers的身高都是独一无二的整数(1..100,000)。

另外老师给tHeem_Lody规定了一个费用,即每次交换两人位置的费用等于两人身高的和。你能帮助tHeem_Lody找出一个最合适的方案,使得他将整个队列按照身高从低到高排成一列后所耗的费用最小吗?

 

输入 (csort.in)

第 1 行: 一个整数 N。

第 2 ..N+1行: 每行包含一个整数,第i+1行描述站在第i个位置的Oiers 的身高。

 

输出 (csort.out)

第 1 行: 将整个队列按照身高从低到高排成一列后所耗的最小费用。

 

样例输入

3

2

3

1

样例输出

7

 

样例说明

3个人,身高分别为2,3,1

第一次交换 1,3,花费1+3=4,队列变成 2 1 3

第二次交换 2,1,花费1+2=3,队列变成1 2 3,完成排队,总花费 3+4=7

题解:排序+找环+统计两种换位方法取最小值

 

 

四、散步 (second.cpp/c/pas)

 

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

描述

烟台的夜晚是很凉爽的,即使是在盛夏。

tHeem_Lody喜欢在熄灯之前跑到校园里一个人散步。他给校园里的n个建筑设定了编号,编号从1到n,并测定了m条小路的距离,保证每条小路连接两个不同的建筑。

设机房的编号为1,宿舍的编号为n,那么tHeem_Lody可以找出一条从机房到宿舍的距离最短的散步路线。但tHeem_Lody希望在熄灯之前回到宿舍的前提下,用更多的时间感受夜晚的凉爽,他不希望走最短的路线,而希望走第二短的路线。

你能够帮助他求出第二最短路线的长度吗?

 

输入 (second.in)

第一行,两个空格隔开的整数n,m

以下m行,每行三个数u,v,l,表示第u和第v号建筑之间存在一条长度为l的小路。

 

对于30%的数据,n<=10

对于70%的数据,n<=80

对于100%的数据,n<=400,0<m<=4950,0<l<=100,000

输出 (second.out)

一行,输出第二最短路的距离

 

样例输入

4 5

1 4 9

1 3 10

2 1 3

2 3 2

4 3 1

样例输出

9

样例说明

最短路是 1->2->3->4   距离为6

第二最短路是 1->4 距离为9

题解:SPFA求最短路+枚举边删除再求最短路取最大

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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