USACO 2013 DEC SILVER
一、题目概览
|
中文题目名称 |
挤奶调度 |
农场航线 |
贝西洗牌 |
|
英文题目名称 |
msched |
vacation |
shuffle |
|
可执行文件名 |
msched |
vacation |
shuffle |
|
输入文件名 |
msched.in |
vacation.in |
shuffle.in |
|
输出文件名 |
msched.out |
vacation.out |
shuffle.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
比较方式 |
全文比较 |
全文比较 |
全文比较 |
二、运行内存限制
|
运行内存上限 |
128 M |
128 M |
128 M |
1.挤奶调度{msched}
【问题描述】
FJ有N(1 <= N <= 10,000)头牛要挤牛奶，每头牛需要花费1单位时间。
奶牛很厌烦等待，奶牛i在它的截止时间d_i (1 <= d_i <= 10,000)前挤g(1 <= g_i <= 1000)的奶，否则将不能挤奶。时间t开始时为0，即在时间t=x时，最多可以挤x头奶牛。
请计算FJ的最大挤奶量。
【文件输入】
第一行，一个整数N。
接下来2..N+1行，每行两个整数，g_i 和 d_i.。
【文件输出】
输出共一行，一个整数，表示最大挤奶量【输入样例】
4
10 3
7 5
8 1
2 1
【输出样例】
25
【样例说明】
奶牛3à奶牛1à奶牛2，奶牛4不挤。
2. 农场航线{ vacation }
【问题描述】
有N(1 <= N <= 200)个农场，用1..N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1..K中的农场作为枢纽(1 <= K <= 100, K <= N)。
当前共有M (1 <= M <= 10,000)条单向航线连接这些农场，从农场u_i 到农场 v_i, 将花费 d_i美元。(1 <= d_i <= 1,000,000).
航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a_i到农场 b_i，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。
请计算可行航行请求的数量，及完成所有可行请求的总费用。
【文件输入】
第一行，四个整数N, M, K和 Q。
接下来2到M+1行，第i+1行包含三个整数u_i, v_i和d_i。
接下来2+M到1+M+Q行: 第1+M+i行表示第i个航行请求。
【文件输出】
第一行，一个整数，表示可行的航行请求数量。
第二行，一个整数，表示完成所有可行航行请求的总费用。
【输入样例】
3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2
【输出样例】
2
24
【样例说明】
第一个请求花费17，第二个请求不可行，第三个请求花费7，总花费24。
3.贝西洗牌{shuffle}
【问题描述】
贝西有一种独门的洗牌方法，称为贝西洗A：
贝西洗A：将一堆共M (2 <= M <= 100,000)张从上到下编号1..M的纸牌，从上到下第i张牌洗到位置p[i]。例M=3，P[1]=3,p[2]=1,p[3]=2,则执行一次洗法A后，从上到下将变为2，3，1,即牌1放到位置3，牌2放到位置1，牌3放到位置2。
贝西现在要练习另外一种更强的洗牌方法，称为贝西洗B，他有一堆N (M <= N <= 100,000)张编号为1..N的牌，并按从上到下1到N的顺序堆放。另有一个堆用来辅助洗牌，称为临时堆，开始时为空。
贝西洗B：（1）将最上面M张牌进行贝西洗A，（2）将最上面的一张牌放到临时堆的最上方；重复（1）（2）操作，直到原先的堆没有牌为止。
以上过程中，当原先堆的牌不足M张的时候，将不进行贝西洗A，而是将最上面的牌依次放到临时堆上。
现在有Q个询问，求临时堆中Qi位置上的牌的编号。
【文件输入】
第一行，三个空格间隔的整数N，M和Q。
第2..1+M行，描述数组P。
第2+M..1+M+Q行， 每行一个整数，表示Qi。
【文件输出】
Q行，每行一个整数，表示第Qi张牌的编号。
【输入样例】
5 3 5
3
1
2
1
2
3
4
5
【输出样例】
4
5
3
1
2
【样例说明】
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (2 放到临时堆)
[3, 1, 4, 5] -> [1, 4, 3, 5] (1放到临时堆)
[4, 3, 5] -> [3, 5, 4] (3放到临时堆)
[5, 4] (5放到临时堆)
[4] (4放到临时堆)