 |
| Contest: FEB08 SILVER Division |
|
| |
ANALYSIS MODE
Submit
solutions for your own enjoyment. **********************************************************************
金组题目
**********************************************************************
编号1~3，共3题
**********************************************************************
题目 1: 路面修整 [Brian Dean, 2008]
FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的
路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能
同时出现在修好的路中。
整条路被分成了N段，N个整数A_1, ... , A_N (1 <= N <= 2,000)依次描述
了每一段路的高度(0 <= A_i <= 1,000,000,000)。FJ希望找到一个恰好含N个
元素的不上升或不下降序列B_1, ... , B_N，作为修过的路中每个路段的高度。
由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为：
|A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|
请你计算一下，FJ在这项工程上的最小支出是多少。FJ向你保证，这个支出
不会超过2^31-1。
程序名: grading
输入格式:
* 第1行: 输入1个整数：N
* 第2..N+1行: 第i+1行为1个整数：A_i
输入样例 (grading.in):
7
1
3
2
4
5
3
9
输出格式:
* 第1行: 输出1个正整数，表示FJ把路修成高度不上升或高度不下降的最小花费
输出样例 (grading.out):
3
输出说明:
FJ将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度
增加到5，总花费为|2-3|+|5-3| = 3，并且各路段的高度为一个不下降序列
1,2,2,4,5,5,9。
**********************************************************************
题目 2: 奶牛的游戏 [Shravas Rao, 2007]
FJ的奶牛们最近发明了一个新的游戏，以此考验FJ。
所有N (2 <= N <= 50,000)头奶牛都站在平面内的某个整点上，奶牛1站在
点(0,0)，FJ知道奶牛2与奶牛1的x坐标的距离(0 <= X_i <= 1,000,000)，以及
她们y坐标的距离(0 <= Y_i <= 1,000,000)。
比如说，奶牛1与奶牛2的x、y坐标的距离为(3, 2)，那么奶牛2的位置可能
为(3, 2)，(-3, 2)，(3, -2)或是(-3, -2)，因为奶牛1的位置为(0, 0)。随后
，FJ依次被告知奶牛2与奶牛3的距离，奶牛3与奶牛4的距离，...，奶牛N-1与
奶牛N的距离。
Farmer John的任务是，在不改动各头奶牛间距离的情况下，通过合理地
安排各头奶牛的位置，使奶牛N与奶牛1之间的x、y坐标距离的和最小。
这是一道提交答案题。对于每一组输入，保证能找到一种安排奶牛的方案，
使得奶牛N所在点恰好就是奶牛1所在点。如果你给出的奶牛安排方案中，奶牛N
与奶牛1之间的x、y坐标距离的和为x，那么你的得分为(1000-x)/1000。输出的
第一行按样例输出的格式，标明当前数据为第CASE (1 <= CASE <= 25)组。
输入数据在此下载.
程序名: cgame
输入格式:
* 第1行: 2个用空格隔开的整数：CASE、N
* 第2..N行: 第i+1行为2个用空格隔开的整数，分别为奶牛i与奶牛i+1的x、y
坐标的距离
输入样例 (cgame.in):
1 5
2 6
3 1
1 4
4 3
输入说明:
一共有5头奶牛。奶牛1与奶牛2的距离为(2, 6)，奶牛2与奶牛3的距离为
(3, 1)，奶牛3与奶牛4的距离为(1, 4)，奶牛4与奶牛5的距离为(4, 3)。
输出格式:
* 第1行: 按该格式输出1行信息：#FILE cgame ID，其中ID为数据编号
* 第2..N+1行: 输出程序求出的最优解中，各头奶牛的位置。第i行为2个用空格
隔开的整数x、y，表示奶牛i的位置
输出样例 (cgame.out):
#FILE cgame 1
0 0
2 -6
5 -7
4 -3
0 0
输出说明:
这个输出可以拿到这个点的满分，因为奶牛1和奶牛N在同一个点，并且奶牛
的相对位置没有违反输入中的规定。
**********************************************************************
题目 3: Hotel [周源, 2007]
奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及
明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的
旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房，它们在同一层
楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的
湖面。
贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，
希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单：
如果存在r满足编号为r..r+D_i-1的房间均空着，他就将这一批顾客安排到这些
房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另
找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。
旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i
描述，表示编号为X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1)房间中的客人全部
离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。
而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共
需要处理M (1 <= M < 50,000)个按输入次序到来的住店或退房的请求。第一个
请求到来前，旅店中所有房间都是空闲的。
程序名: hotel
输入格式:
* 第1行: 2个用空格隔开的整数：N、M
* 第2..M+1行: 第i+1描述了第i个请求，如果它是一个订房请求，则用2个数字
1、D_i描述，数字间用空格隔开；如果它是一个退房请求，用3
个以空格隔开的数字2、X_i、D_i描述
输入样例 (hotel.in):
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
输出格式:
* 第1..??行: 对于每个订房请求，输出1个独占1行的数字：如果请求能被满足
，输出满足条件的最小的r；如果请求无法被满足，输出0
输出样例 (hotel.out):
1
4
7
0
5
**********************************************************************
Translation by Yan Long