276 lines
5.5 KiB
Markdown
276 lines
5.5 KiB
Markdown
``` markdown
|
||
1（必做） 二维极大点问题 *
|
||
Score 100
|
||
在一个二维平面上，如果有两个点(x1,y1)和(x2,y2)，有比较关系x1>x2且y1>y2，则称点(x1,y1)支配了(x2,y2)，(x1,y1)是极大点。
|
||
当比较关系修改为x1≥x2且y1≥y2时，支配关系会产生有趣的变化，下面考虑这种情况。对于给定n个点的集合，编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。
|
||
|
||
输入格式:
|
||
输入包括两行，第一行是正整数n，表示是点的个数，第二行包含n个点的坐标，坐标值都是整数，x坐标和y坐标范围从0到1000，且输入数据中不存在坐标相同的点。
|
||
|
||
输出格式:
|
||
按x轴坐标最小到大的顺序输出所有极大点。
|
||
输出格式为:(x1,y1)(x2,y2)...(xk,yk)
|
||
|
||
输入样例:
|
||
5
|
||
1 2 2 2 3 1 2 3 1 4
|
||
输出样例:
|
||
(1,4)(2,3)(3,1)
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
400 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
```
|
||
|
||
---
|
||
|
||
``` markdown
|
||
2 递归算法解决自然数拆分问题
|
||
Score 100
|
||
|
||
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，试求n的所有拆分。
|
||
|
||
输入格式:
|
||
输入大于1的自然数n。
|
||
|
||
输出格式:
|
||
输出包含多行，每行为自然数n的一种拆分，表示为加法式的形式，以拆分数非递减的次序输出。
|
||
|
||
输入样例1:
|
||
5
|
||
输出样例1:
|
||
1+4
|
||
1+1+3
|
||
1+1+1+2
|
||
1+1+1+1+1
|
||
1+2+2
|
||
2+3
|
||
输入样例2:
|
||
7
|
||
输出样例2:
|
||
1+6
|
||
1+1+5
|
||
1+1+1+4
|
||
1+1+1+1+3
|
||
1+1+1+1+1+2
|
||
1+1+1+1+1+1+1
|
||
1+1+1+2+2
|
||
1+1+2+3
|
||
1+2+4
|
||
1+2+2+2
|
||
1+3+3
|
||
2+5
|
||
2+2+3
|
||
3+4
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
400 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
---
|
||
|
||
``` markdown
|
||
3 诚实人调查问题
|
||
Score 100
|
||
有N个人，其中某些人是诚实的其他人可能会说谎。现在需要进行一项调查，该调查由一系列测试构成，每次测试如下进行：选2个人，然后提问：对方是否诚实？每个人的回答只能是“是”或者“否”。假定在这些人中，所有诚实的人回答都是正确的，而其他人的回答则不能肯定是否正确。如果诚实的人数>N/2，试设计一个调查算法，以最小的测试次数从其中找出一个诚实的人。
|
||
|
||
输入格式:
|
||
第一行为一个不超过100的正整数N，表示参与调查的总人数；接下来的N行，每行或者是1或者是0（其中1代表诚实的人，0代表会说谎的人，注意1的个数>N/2）。
|
||
|
||
输出格式:
|
||
正整数K，表示第K个人是诚实的。
|
||
(若有多个答案，请输出最小的一个,如输入样例的对应答案11，12，15，16均满足，其中最小的为11)
|
||
|
||
输入样例:
|
||
在这里给出一组输入。例如：
|
||
|
||
16
|
||
1
|
||
0
|
||
1
|
||
0
|
||
1
|
||
1
|
||
0
|
||
0
|
||
1
|
||
0
|
||
1
|
||
1
|
||
1
|
||
0
|
||
1
|
||
1
|
||
输出样例:
|
||
在这里给出相应的输出。例如：
|
||
|
||
11
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
400 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
```
|
||
|
||
``` markdown
|
||
4（必做） 带有期限的作业调度问题 *
|
||
Score 100
|
||
带有期限的作业调度问题要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题，形式化描述为：
|
||
|
||
只能在一台机器上处理 n 个作业，每个作业 i=1,...,n 均可在单位时间内完成。
|
||
每个作业 i 都有一个期限值 d
|
||
i
|
||
|
||
>0，（ d
|
||
i
|
||
|
||
是整数）。
|
||
当且仅当作业 i 在它的截止期限前被完成时获得 p
|
||
i
|
||
|
||
>0 的效益；
|
||
问题的可行解是这 n 个作业的一个子集合。集合中的每个作业都能在各自的截止期限之前完成，产生一个作业效益之和 ∑p
|
||
i
|
||
|
||
。具有最大效益值的可行解就是最优解。
|
||
输入格式:
|
||
第一行为一个正整数n，表示作业的个数；
|
||
接下来的 n 行，每行两个正整数（中间用空格隔开），表示每个作业 i 的截止期限 d
|
||
i
|
||
|
||
和按期完成产生的效益p
|
||
i
|
||
|
||
。
|
||
输出格式:
|
||
一行一个整数，给出最优解的效益值。
|
||
输入样例1:
|
||
4
|
||
1 20
|
||
2 15
|
||
2 100
|
||
1 10
|
||
输出样例1:
|
||
120
|
||
输入样例2:
|
||
6
|
||
2 25
|
||
3 20
|
||
3 15
|
||
2 10
|
||
4 1
|
||
4 5
|
||
输出样例2:
|
||
65
|
||
数据范围
|
||
d
|
||
i
|
||
|
||
≤n≤10
|
||
6
|
||
,p
|
||
i
|
||
|
||
≤10
|
||
9
|
||
|
||
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
1000 ms
|
||
Memory Limit
|
||
512 MB
|
||
Stack size limit
|
||
8192 KB
|
||
```
|
||
|
||
``` markdown
|
||
5 买股票问题
|
||
Score 100
|
||
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
|
||
对该股票可以进行多次买卖操作，请设计一个算法,来计算所能获取的最大利润。注意，在对该股票买卖操作过程中,要求在再次购买前,出售掉之前的股票。
|
||
|
||
输入格式:
|
||
第 1 行1个整数n, 表示数组元素数。
|
||
|
||
第2行n个整数，表示股票价格。
|
||
|
||
输出格式:
|
||
一个整数，表示所能获得的最大利润。
|
||
|
||
输入样例1:
|
||
6
|
||
7 1 5 3 6 4
|
||
输出样例1:
|
||
7
|
||
解释：在第 2 天买入，在第 3 天卖出, 获得利润 = 5-1 = 4 。随后，在第 4 天买入，在第 5 天卖出, 获得利润 = 6-3 = 3 。
|
||
|
||
输入样例2:
|
||
5
|
||
1 2 3 4 5
|
||
输出样例2:
|
||
4
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
400 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
```
|
||
|
||
|
||
``` markdown
|
||
6 集合问题
|
||
Score 100
|
||
给定n个集合A1，A2，…，An，每个集合都由连续的正整数构成，即
|
||
Ai={x| ai<= x<= bi}， i=1,2,...,n
|
||
设计一个算法求最小的集合S，使得对每个i=1,2,...,n，|S ∩Ai|≠∅,即每个Ai至少含有S中的一个数。
|
||
|
||
输入格式:
|
||
第1行是n，表示集合的个数；
|
||
第2行到第n+1行分别是这n个集合的最小正整数和最大正整数。
|
||
|
||
输出格式:
|
||
第1行是集合S，按照从小到大的顺序。
|
||
|
||
输入样例1:
|
||
5
|
||
1 6
|
||
3 4
|
||
2 8
|
||
4 10
|
||
3 7
|
||
输出样例1:
|
||
4
|
||
输入样例2:
|
||
5
|
||
1 7
|
||
7 9
|
||
5 8
|
||
2 6
|
||
9 10
|
||
输出样例2:
|
||
6 9
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
100 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
|
||
``` |