此題就是要在給定區間[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 閱讀(478)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構