此題就是要在給定區(qū)間[s,t]中整點(diǎn)位置最少種植k個(gè)西瓜，問(wèn)最少需要多少瓜，給定區(qū)間可以重疊。
具體做法：按區(qū)間右端點(diǎn)坐標(biāo)從前向后排序，如果右端點(diǎn)相同，比較左端點(diǎn)，左端點(diǎn)小的排前面。在每個(gè)區(qū)間上從后向前種，直到達(dá)到這個(gè)區(qū)間的最小要求。
說(shuō)實(shí)話，這類題目雖然很容易想到貪心，但是對(duì)于以什么規(guī)則對(duì)區(qū)間進(jìn)行排序我不是多么擅長(zhǎng)……很囧。
以下是我的代碼：
#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;
}