神马品牌网现代简约装饰画贴图:贪心算法，PASCAL高手进
来源：百度文库 编辑：神马品牌网 时间：2024/04/30 18:21:08
第1题
一条街的一边有几座房子。居民想在路边种树，路边的地区被分成块，并被编号为1..n。每个块的大小为一个单位尺寸最多可种植一颗树。一些居民提出要求，格式是三个数b，e，t即在b与e间要种t棵树，这里b<=e,t<=e-b+1。
Input
第一行包含数据n，表示区域的个数（0< n< = 30000）。第二行一个数h，表示有多少居民提出要求（0 < h< = 5000）。接下来的每行是三个数b，e，t。（ 0 < b < = e < = n,t < = e-b+1）。
Output
一个整数即为了满足所有提出的要求最少需要种树的数目。
Sample Input
9
4
1 4 2
4 6 2
8 9 2
3 5 2
Sample Output
5
第2题
一个正整数一般可分为几个互不相同的自然数的和，如3＝1＋2；6＝1＋3＝2＋4…。你的任务是将正整数n分解成若干各互不相同的自然数的和，且使这些自然数的乘积最大。
Input
输入：只有一个正整数n。（3<=n<=10000）。
Output
第一行是分解方案，相邻的数之间用空格隔开，且由小到大排序。
第二行是最大的乘积。
Sample Input
10
Sample Output
2 3 5
30
一条街的一边有几座房子。居民想在路边种树，路边的地区被分成块，并被编号为1..n。每个块的大小为一个单位尺寸最多可种植一颗树。一些居民提出要求，格式是三个数b，e，t即在b与e间要种t棵树，这里b<=e,t<=e-b+1。
Input
第一行包含数据n，表示区域的个数（0< n< = 30000）。第二行一个数h，表示有多少居民提出要求（0 < h< = 5000）。接下来的每行是三个数b，e，t。（ 0 < b < = e < = n,t < = e-b+1）。
Output
一个整数即为了满足所有提出的要求最少需要种树的数目。
Sample Input
9
4
1 4 2
4 6 2
8 9 2
3 5 2
Sample Output
5
第2题
一个正整数一般可分为几个互不相同的自然数的和，如3＝1＋2；6＝1＋3＝2＋4…。你的任务是将正整数n分解成若干各互不相同的自然数的和，且使这些自然数的乘积最大。
Input
输入：只有一个正整数n。（3<=n<=10000）。
Output
第一行是分解方案，相邻的数之间用空格隔开，且由小到大排序。
第二行是最大的乘积。
Sample Input
10
Sample Output
2 3 5
30