请访问TOJ查看最终排名：http://10.60.101.7

Thank you for your participating!!

[ 本帖最后由 firepot 于 2008-5-11 00:43 编辑 ]

顶～～可惜软件的太少了点

前半部分 06的好少。。。难道06真是没落的一代？。。。。

07很强大

请问谁有竞赛负责人的联系方式,
我有东西拉在赛场忘拿走了,有人看到吗?

期待 咕噜姐少男 暴联系方式

shek & gragon 请客
昨天中午你们走了以后还真有两个MM冲过来问咕噜姐有没有女朋友

通过这次比赛，咕噜姐完全出名了

引用:

原帖由 NSBirdsong 于 2008-5-11 19:30 发表
shek & gragon 请客
昨天中午你们走了以后还真有两个MM冲过来问咕噜姐有没有女朋友

引用:

原帖由 NSBirdsong 于 2008-5-11 19:30 发表
shek & gragon 请客
昨天中午你们走了以后还真有两个MM冲过来问咕噜姐有没有女朋友

晕 这么强大 很好 值得炒作 鸟爷 努力炒作炒作 让咕噜姐冲出亚洲 走向世界

引用:

原帖由 ro9er 于 2008-5-11 21:00 发表

晕 这么强大 很好 值得炒作 鸟爷 努力炒作炒作 让咕噜姐冲出亚洲 走向世界

好主意
我们要把咕噜姐少男精神发扬光大

引用:

原帖由 shek 于 2008-5-11 21:42 发表

好主意
我们要把咕噜姐少男精神发扬光大

Good Idea!

关于校内赛第二题，当天提交人数非常多，但是通过的却很少。赛后也有很多同学问我这个题目的数据有什么陷阱之类的。其实数据是没有任何问题的，只是方法不够正确。大多数队伍都是在一些针对贪心的数据上挂了。judge的时候我看过一些同学的代码，基本上都是用贪心做的。（有一个AC的队貌似是用贪心过的，代码比较复杂。希望这个队伍来讲讲他们贪心策略，如果没有记错，应该是CH3CHO他们队）

事实上，这个题目有一个很直接的做法就是枚举最优方案中最高和最矮的小塔高度，然后判断这个方案是否可行。
假设当前枚举的最高和最矮的小塔高度分别为maxNow, minNow, 另外保存一个零时变量cancel (init = 0)那么只需要一遍扫描，判断当前高度currHeight.
if currHeight > maxNow
   cancel += currHeight - maxNow
if currHeight < minNow
  cancel += currHeight
最后只需要判断cancel <= M 那么这就试一组有效解。
在所有有效解中选择一个 maxNow - minNow最小的，即为最优解。

引用:

原帖由 NSBirdsong 于 2008-5-12 12:17 发表
关于校内赛第二题，当天提交人数非常多，但是通过的却很少。赛后也有很多同学问我这个题目的数据有什么陷阱之类的。其实数据是没有任何问题的，只是方法不够正确。大多数队伍都是在一些针对贪心的数据上挂了。judge的 ...

多谢鸟爷

当时B我们很RP的一次过了。。。

ls 讲讲你们的贪心策略，让大家分享一下嘛~
judge的时候没怎么仔细看你们B的代码，就觉得用了一些很神奇的判断（除法都用上了），然后就AC了........

其实这题还是有O(n)的枚举的。Dirdsong一不小心就出了道猛题

引用:

原帖由 houston 于 2008-5-11 12:49 发表
前半部分 06的好少。。。难道06真是没落的一代？。。。。

别人不知道。。。反正我们班的高手都没去。。。我这种草根去了。。
就因为B题浪费了光阴。。。。罚时太多与35名擦肩而过。。
另：为什么都在软院版里讨论啊。。可怜的电信。。。

引用:

我承认我看贴不仔细，刚刚看到鸟爷的#13和#16，我认罪。。。。。。

我们对于B题的思路么，就是这样的。。。

引用:

首先肯定是要对小塔们按高度排序，记录当前最高的小塔与最矮的小塔的高度差，并将这个序列和对应的剩余可消高度入队列，之后一切操作针对这两个个队列里的元素进行。
将一个小塔序列和它对应的剩余可消高度出队列，之后进行如下两个操作：一，如果剩余可消高度足以将序列中最矮的小塔削平，削之，将结果再入队列；二，如果剩余可消高度足以将最高的几个小塔的高度同时消减，消之，不过最多将这些小塔消到与第二高的小塔高度一致，将结果入队列。直到队列为空，操作结束。当然，没得到一个中间结果，那么就要与当前那个高度差的最小值进行比较，记录那个较小的为当前的最小值。

这个思路大部分出自TJQ同学，因为题目的时间限制比较长么，这种效率比较低的算法也能通过，STL容器的效率实在不敢恭维啊。当时写完这道题目，我基本就透支了，大脑一片混乱，点下提交的时候就基本等待WA，打印都准备好了，不过还是RP的AC了，哎哎。。。。

[ 本帖最后由 CH3CHO 于 2008-5-25 06:01 编辑 ]

LS的意思是
用两种策略不停的贪心直到贪不了为止？