USACO 2012 JAN（题目二）
一、题目概览
|
中文题目名称 |
叠干草 |
分干草 |
奶牛联盟 |
|
英文题目名称 |
stacking |
baleshare |
cowrun |
|
可执行文件名 |
stacking |
baleshare |
cowrun |
|
输入文件名 |
stacking.in |
baleshare.in |
cowrun.in |
|
输出文件名 |
stacking.out |
baleshare.out |
cowrun.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
比较方式 |
全文比较 |
全文比较 |
全文比较 |
二、运行内存限制
|
运行内存上限 |
128 M |
128 M |
128 M |
注：感谢老胡鼎力翻译。【错误会有的，语句也不是那么流畅……】
1.叠干草{Bronze题2}
【问题描述】
有(1 <= N <= 1,000,000, N为奇数)堆干草，按1..N编号，开始时每堆高度都是0，FJ给出K (1 <= K <= 25,000)条指令，每条指令包含两个用空格隔开的整数，例如”10 13”，表示给10,11,12,13这四堆干草分别叠加一捆干草，即高度均增加1。
FJ想知道，干草对完后，这N堆干草高度的中位数是多少。
【文件输入】
第一行，两个正整数N和K。
第2..K+1行，每行两个整数A B (1 <= A <= B <= N)，表示一条指令。
【文件输出】
一个整数，表示中位数。
【输入样例】
7 4
5 5
2 4
4 6
3 5
【输出样例】
1
【样例说明】
堆完后，高度分别是0,1,2,3,3,1,0。排序后为0,0,1,1,2,3,3，故中位数是1。
2.分干草{silver题2}
【问题描述】
FJ有N (1 <= N <= 20)包干草，干草i的重量是 S_i (1 <= S_i <= 100)，他想尽可能平均地将干草分给3个农场。
他希望分配后的干草重量最大值尽可能地小，比如， B_1,B_2和 B_3是分配后的三个值，假设B_1 >= B_2 >= B_3，则他希望B_1的值尽可能地小。
例如：8包感触的重量分别是：2 4 5 8 9 14 15 20，一种满足要求的分配方案是
农场 1: 2 9 15 B_1 = 26
农场 2: 4 8 14 B_2 = 26
农场 3: 5 20 B_3 = 25
请帮助FJ计算B_1的值。
【文件输入】
第一行，一个整数N。
第2..N+1行，每行一个整数，表示重量。
【文件输出】
一行，一个整数，表示B_1的值。
【输入样例】
8
14
2
5
15
8
9
20
4
【输出样例】
26
3. 奶牛跑步{ Gold题2}
【问题描述】
FJ和贝茜为奶牛们设计了一个新的跑步游戏。跑道是环行的，长度为(2 <= M <= 1,000,000,000)的环行，奶牛们在相同的起跑位置。这个游戏一共要进行N (1 <= N <= 14)轮，通过一副8N张的纸牌来控制每一轮的跑步距离，每张纸牌都有一个数字X_i (0 <= X_i < M)。
每一轮，FJ取出最上面的8张纸牌，然后再取出这8张的上面或者底下的4张。接着，贝茜从这4张牌中取出上面或者底下的2张，上面一张的数字为X_top，下面一张的数字是X_bottom，则牛先跑R*X_top的距离（R表示奶牛们已经跑过的距离），再跑X_bottom的距离。
FJ担心奶牛们太累而回不到起点，游戏结束时，若奶牛们离开起点距离超过K (0 <= K <=floor(M/2))，则他们就回不了起点了。
问题保证，当FJ选择正确的取牌策略，不论贝西如何取牌，奶牛们都能够回到起点。对于每一轮，你的任务是决定取哪4张纸牌。在输入数据中，贝西的每次选择都是已知的，但FJ的每次取牌时，贝西接着的选择应该被假定为是未知的，即不论贝西怎么选，FJ的选择都是能保证奶牛们能够回到起点。
【文件输入】
第一行，3个用空格隔开的整数N，M，K。
第二行，N个字符，若第i个字符是T，表示第i轮贝西选择上面的2张纸牌，若是B，则表示选择下面的2张纸牌。
第3..N+2行，每行包含8个数字，表示每一轮开始时，最上面的8张纸牌（自上而下）上的数字。
【文件输出】
一行，一个包含N个字符的字符串，若第i个字符是T，表示第i轮FJ选择上面的4张纸牌，若是B，则表示选择下面的4张纸牌。若有多解，则输出字典序最小的方案。
【输入样例】
2 2 0
TT
1 0 0 0 0 0 0 1
0 1 1 1 0 0 1 0
【输出样例】
TB
【样例说明】
注意，FJ在选择纸牌前，他被当做是不知道贝西接下来的选择的，否则他两次都可以选择B。