回复 楼主 sunyh1999
解题方法:
想要种树种得少，就要让一棵树给多个区间使用，这样，尽量在叠加区间种树。
处理问题时，先按所有区间的开始位置从小到大排序，若开始位置相同，则按照结束位置由大到小排序。
之后依次逆序处理每个区间，由于重叠位置一定是区间开始处，所以先在倒数第一个区间开始处种满足要求的树，对前一个区间，看差多少棵就在该区间开始处补种多少。
最后统计树的总数即可！
代码现在贴出，请大家测试：
程序代码：
#include <stdio.h>
#include <stdlib.h>
int tree[30001]; /* 0表示该位置没有树，1表示该位置有树 */
int a[5001][3]={0}; /* b,c,t */
int n,h; /* 区域的个数、房子的数量 */
int sum=0;
int plant(int home,int num)
{
int i;
for(i=home;i<=30000;i++)
{
if(tree[i])
{
continue;
}
else
{
tree[i]=1;
num--;
if(!num)break;
}
}
return 0;
}
int count(int home,int end)
{
int i,num=0;
for(i=home;i<=end;i++)
if(tree[i])
num++;
return num;
}
long int hsort(int *p,int *q)
{
long x,y;
x=*p*30000+(30000-*(p+1));
y=*q*30000+(30000-*(q+1));
return x-y;
}
main()
{
int i;
LOOP:
printf("请输入区域的个数：（输入0则退出）");
scanf("%d",&n); /*输入区域的个数*/
if(n==0)exit(0);
for(i=0;i<=n;i++) /*初始化所有位置没有树*/
tree[i]=0;
printf("请输入房子的数目：");
scanf("%d",&h); /*输入房子的数目*/
printf("请输入描述居民的需要b c t :(0<b<c<30,000，t<c-b+1)。");
for(i=0;i<h;i++) /*分别输入n条纸带起点与终点*/
{
scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
}
qsort(a, h, sizeof(a[0]), hsort); /*按照起点快速升序排序，如遇起点相同，则按末点降序*/
/* 最后一间房子的树从起点开始种 */
plant(a[h-1][0],a[h-1][2]);
/* 倒数第二间房子依次向前逐个判断 */
for(i=h-2;i>=0;i--)
{
/* 判断已经种上的树是否足够 */
if(count(a[i][0],a[i][1])>=a[i][2])
continue; /*如果足够，则继续*/
else /*否则，从左端开始找空位种够要求的树*/
plant(a[i][0],a[i][2]-count(a[i][0],a[i][1]));
}
sum=count(1,n);
printf("最少树的数量为：%d\n",sum);
goto LOOP;
}
[
本帖最后由 jack10141 于 2010-9-9 23:39 编辑 ]
