POJ 1065 Wooden Sticks#贪心+qsort用法

(~ ̄▽ ̄)~*

这道题用到了cstdlib库的qsort()函数

用法链接:http://www.cnblogs.com/syxchina/archive/2010/07/29/2197382.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std; struct stick
{
int l,w;
int flag;
}st[5005]; int cmp(const void *u,const void *v)
{
stick *a=(stick *)u;
stick *b=(stick *)v;
if(a->l == b->l)
return a->w - b->w;
else
return a->l - b->l;
} int main()
{
int cas,n,minT,W;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&st[i].l,&st[i].w);
st[i].flag=0;
}
qsort(st,n,sizeof(st[0]),cmp); //从小到大排序,如果l相等,则w小的排前 minT=0;
for(int i=0;i<n;i++)
{
if(!st[i].flag)
{
minT++;
W=st[i].w;
for(int j=i+1;j<n;j++)
{
if((!st[j].flag)&&st[j].w>=W)
{
st[j].flag=1;
W=st[j].w;
}
}
}
}
printf("%d\n",minT);
}
return 0;
}
上一篇:How to delete expired archive log files using rman?


下一篇:[Android FrameWork 6.0源码学习] View的重绘过程之Draw