NOIp Senior Day2
zhzh2001
题目名称 围栏 Quicksort Killer 花园改造
目录 corral qkiller landscape
可执行文件名 corral qkiller landscape
输入文件名 corral.in qkiller.in landscape.in
输出文件名 corral.out qkiller.out landscape.out
时间限制 1s 1s 1s
空间限制 512MB 512MB 512MB
测试点数量 20 10 20
测试点分数 5 10 5
比较方式 全文 SPJ 全文
部分分 无 无 无
提交源程序文件名
对于 C++ 语言 corral.cpp qkiller.cpp landscape.cpp
对于 C 语言 corral.c qkiller.c landscape.c
对于 Pascal 语言 corral.pas qkiller.pas landscape.pas
编译选项
对于 C++ 语言 -O2 -std=gnu++11 -O2 -std=gnu++11 -O2 -std=gnu++11
对于 C 语言 -O2 -O2 -O2
对于 Pascal 语言 -O2 -O2 -O2
注意事项：
1. 注意编译选项，避免未定义行为或编译错误。
2. 代码长度限制为 100KB。
3. 注意代码常数和 I/O 造成的效率影响。
1
1 围栏 (CORRAL.C/CPP/PAS) 2
1 围栏 (corral.c/cpp/pas)
1.1 题目描述
农夫约翰打算建造一个围栏来圈养他的奶牛。作为最挑剔的兽类，奶牛们要求这个
围栏必须是正方形 的，并且围栏里至少 要有 C 个草场，来供应它们的食物。
约翰的土地上一共有 N 个草场 (1 ≤ C ≤ N ≤ 3, 000)，每个草场都在一块1x1 的方
格 内，坐标范围 0 . . . 10
18
。如果有多个草场在同一个方格内，那么它们的坐标就会相同。
请帮助约翰计算围栏的最小边长。
1.2 输入格式 (corral.in)
第一行两个整数 C, N 。
接下来 N 行，每行两个整数，表示一个草场所在方格的坐标。
1.3 输出格式 (corral.out)
输出最小边长。
1.4 输入样例
3 4
1 2
2 1
4 1
5 2
1.5 输出样例
4
1.6 样例解释
围栏左上角坐标可以为 (1,1)，边长为 4，此时前三个草场都在围栏内。更小的边长
不能满足要求。
1 围栏 (CORRAL.C/CPP/PAS) 3
1.7 数据范围
测试点 N 坐标范围
1
≤ 5
0 . . . 10
2 0 . . . 10
18
3 ≤ 10 0 . . . 1, 000
4
≤ 50
0 . . . 50
5 0 . . . 200
6 0 . . . 10
18
7
≤ 200
0 . . . 200
8 0 . . . 5, 000
9 0
. . .
10
18
10
≤ 500
0 . . . 500
11 0 . . . 5, 000
12 0 . . . 10
18
13
≤ 1, 000
0 . . . 5, 000
14 0 . . . 10
18
15
≤ 2, 000
0 . . . 500
16 0 . . . 10
18
17
≤ 3, 000
0 . . . 200
18
0 . . . 1, 000, 000, 000
19
20 0 . . . 10
18
2 QUICKSORT KILLER(QKILLER.C/CPP/PAS) 4
2 Quicksort Killer(qkiller.c/cpp/pas)
2.1 题目描述
快速排序是一种广为使用的排序算法，其最好和平均时间复杂度均为 Θ(N log N)，
但是最坏时间复杂度可达 Θ(N
2
)。为了简化问题，我们考虑给 N 个 32 位随机 整数排
序 (N = 100, 000)。
你的任务是，给定这 N 个整数，重新排列 这些整数，使得特定的快速排序实现运
行时间超过 1s。
我们考虑一种常见的实现，来自Free Pascal 的示例代码：
1: procedure Sort(A, l, r) ▷ 对 A[l . . . r] 排序
2: i ← l
3: j ← r
4: x ← A[F(l, r)] ▷ x 为基准值
5: repeat
6: while A[i] < x do
7: i ← i + 1
8: end while
9: while x < A[j] do
10: j ← j − 1
11: end while
12: if i ≤ j then
13: Swap(A[i], A[j])
14: i ← i + 1
15: j ← j − 1
16: end if
17: until i > j
18: if l < j then
19: Sort(l, j)
20: end if
21: if i < r then
22: Sort(i, r)
23: end if
24: end procedure
其中F(l, r) 返回一个 [l, r] 之间的数，作为基准值的下标。这里，你需要考虑四
种实现：
2 QUICKSORT KILLER(QKILLER.C/CPP/PAS) 5
1. F(l, r) = (l + r) / 2
2. F(l, r) = l
3. F(l, r) = r
4. F(l, r) = random(l, r)
上述除法为整数除法，random(l, r) 函数返回 [l, r] 间的伪随机数。随机函数的工
作原理如下：
在程序开始时，自动初始化随机数种子 x
0
= time(NULL)，time(NULL) 函数同
C/C++ 中同名函数，即返回从UTC 1970/01/01 00:00:00 开始到调用时经过的秒数。
(不必考虑闰秒等问题)
random(l, r) 函数第 i 次调用时 x
i
= x
i−1
∗ 48, 271 mod 2, 147, 483, 647(即
minstd_rand)，返回值为 x
i
mod (r − l + 1) + l。
2.2 输入格式 (qkiller.in)
第一行一个整数 type(type ∈ [1, 4])，表示 F 函数的实现。
如果 type = 4，接下来一行一个时间，格式为yyyy/mm/dd hh:mm:ss，表示调用时
间，范围从 UTC 1970/1/1 00:00:00 到 2020/12/31 23:59:59。
接下来一行 N 个整数，在 32 位有符号整数范围内。
2.3 输出格式 (qkiller.out)
输出 N 个符合要求的整数。
2.4 数据范围
测试点 type 整数范围
1
=1
[−2
31
, 2
31
)
2 [−10
8
, 10
8
]
3
=2
[−2
31
, 2
31
)
4 [−1, 000, 1, 000]
5
=3
[−2
31
, 2
31
)
6 [−1, 000, 1, 000]
7
=4
[−2
31
, 2
31
)
8
[−10
8
, 10
8
]9
10
对于 100% 的数据，整数都在对应的范围内等概率随机 生成。
3 花园改造 (LANDSCAPE.C/CPP/PAS) 6
3 花园改造 (landscape.c/cpp/pas)
3.1 题目描述
农夫约翰正在建造一个漂亮的花园，并且在这个工程中需要移动大量的泥土。
这个花园可以看作一个由 N 个花坛组成的序列 (1 ≤ N ≤ 100, 000)，花坛 i 最初
包含 A
i
个单位的泥土。农夫约翰想要改造这个花园，使得花坛 i 包含 B
i
个单位的泥
土。A
i
, B
i
都是 0 . . . 50 之间的整数。
为了改造花园，农夫约翰有几种选项：
• 花费 X 元购买一个单位泥土，并把它放在一个他选择的花坛中。
• 花费 Y 元移除他选择的花坛中一个单位泥土，并把它运走。
• 花费 Z ∗ |i − j| 元把一个单位泥土从花坛 i 运送到花坛 j。
请计算完成改造计划的最小花费。
3.2 输入格式 (landscape.in)
第一行四个整数 N, X, Y, Z(0 ≤ X, Y ≤ 10
8
; 0 ≤ Z ≤ 1, 000)。
接下来 N 行，每行两个整数 A
i
, B
i
。
3.3 输出格式 (landscape.out)
输出完成改造计划的最小花费。
3.4 输入样例
4 100 200 1
1 4
2 3
3 2
4 0
3.5 输出样例
210
3.6 样例解释
有一个单位的泥土必须被移除 (从第四个花坛)，花费 200 元。剩下的泥土可以花
费 10 元移动 (三个单位泥土从第四个花坛到第一个，一个单位从第三个到第二个)。
3 花园改造 (LANDSCAPE.C/CPP/PAS) 7
3.7 数据范围
测试点 N A
i
, B
i
1 ≤ 3 ≤ 3
2 ≤ 4 ≤ 4
3 ≤ 5
≤ 5
4
≤ 10
5
≤ 10
6 ≤ 20
7 ≤ 30
8 ≤ 50
9
≤ 100
10 ≤ 20
11 ≤ 30
12
≤ 50
13 ≤ 500
14 ≤ 1, 000
15 ≤ 2, 000
16 ≤ 5, 000
17 ≤ 20, 000
18 ≤ 50, 000
19
≤ 100, 000
20
