USACO 2012 JAN（题目二）

一、题目概览

二、运行内存限制

      注：感谢老胡鼎力翻译。【错误会有的，语句也不是那么流畅……】

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。

USACO翻译：USACO 2012 JAN三题（2）