此题就是要在给定区间[s,t]中整点位置最少种植k个西瓜，问最少需要多少瓜，给定区间可以重叠。
具体做法：按区间右端点坐标从前向后排序，如果右端点相同，比较左端点，左端点小的排前面。在每个区间上从后向前种，直到达到这个区间的最小要求。
说实话，这类题目虽然很容易想到贪心，但是对于以什么规则对区间进行排序我不是多么擅长……很囧。
以下是我的代码：
#include<stdio.h>
typedef struct
{
long begin,end,num;
}node;
void qsort(node a[],long begin,long end)
{
long i=begin,j=end,mid1=a[(begin+end)/2].end,mid2=a[(begin+end)/2].begin;
node t;
do{
while(a[i].end<mid1||(a[i].end==mid1&&a[i].begin<mid2)) i++;
while(a[j].end>mid1||(a[j].end==mid1&&a[j].begin>mid2)) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(i<end) qsort(a,i,end);
if(j>begin) qsort(a,begin,j);
}
int main()
{
long n,h,i,j,tmp,s[5001]={0},ans=0;
node a[3001];
scanf("%ld%ld",&n,&h);
for(i=1;i<=h;i++)
scanf("%ld%ld%ld",&a[i].begin,&a[i].end,&a[i].num);
// Read In
qsort(a,1,h);// Qsort
for(i=1;i<=h;i++)
{
tmp=0;
for(j=a[i].end;j>=a[i].begin;j--)
if(s[j]==1)
tmp++;
while(tmp<a[i].num)
{
for(j=a[i].end;j>=a[i].begin;j--)
if(s[j]==0)
{
s[j]=1;
tmp++;
if(tmp==a[i].num)
break;
}
}
}
tmp=0;
for(i=1;i<=n;i++)
if(s[i]==1)
tmp++;
printf("%ld\n",tmp);
// getchar();getchar();
return 0;
}posted on 2010-01-06 19:22
lee1r 阅读(427)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构