本文主要是介绍poj 2376（贪心加快排），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<stdio.h>
typedef struct
{
int front,rear;
}Cow;
Cow cow[25050];
int max(int a,int b)
{
return a>b?a:b;
}
void qsort(int l,int r)//快速排序，l代表要排列数据的最左端(left)，r代表要排列数据的最右端(right)
{
int i,j;
Cow x;
if(l<r)
{
i=l;
j=r;
x=cow[l];
while(i<j)
{
while(i<j&&cow[j].front>=x.front)
j--;
if(i<j)
cow[i++]=cow[j];
while(i<j&&cow[i].front<x.front)
i++;
if(i<j)
cow[j--]=cow[i];
}
cow[i]=x;
qsort(l,i-1);
qsort(i+1,r);
}
return ;
}
int main(void)
{
int N,M,i,j,end,count,begin,index,flag;
Cow temp;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
{
scanf("%d%d",&cow[i].front,&cow[i].rear);
}
qsort(0,N-1);
end=0;//每次循环结束，区间最远可以覆盖到多远
count=0;//表示需要几头牛
begin=0;//每次循环，可选牛的起始点最远距离
index=0;//从哪头牛开始
flag=0;//标记
while(end<M)
{
begin=end+1;
for(i=index;i<N;i++)
{
if(cow[i].front<=begin)
{
if(cow[i].rear>=begin)
{
end=max(end,cow[i].rear);
}
}
else
{
index=i;
break;
}
}
if(begin>end)
{
printf("-1\n");
flag=1;
break;
}
else
{
count++;
}}
if(!flag)
printf("%d\n",count);
}
这篇关于poj 2376（贪心加快排）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
