POJ 1065 木棍问题 贪心算法

算法分析：先对木棍结构体数组按照l排序，消除一个变量的干扰，然后再找w连续上升的子序列。用临时变量temp，遇到更大的作更新，且标记为0，采用贪心策略去找有几个连续上升的子序列

#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct stick{
	int l;
	int w;
}stick;
int cmp(const void *a,const void *b)
{
    if((*(stick *)a).l==(*(stick *)b).l)
    {
        return (*(stick *)a).w-(*(stick *)b).w;
    }
    else
    {
        return (*(stick *)a).l-(*(stick *)b).l;
    }
}
int main(){
	int n,m,i,j,sum,temp;
	stick p[5002];
	cin>>n;
	while(n--){
		sum = 0;
		cin>>m;
		for (i = 0;i < m;i++)
		{
			cin>>p[i].l>>p[i].w;
		}
		//先对结构体数组按照l排序，消除一个变量的干扰，然后再找w连续上升的子序列
		qsort(p,m,sizeof(stick),cmp);
		for (i = 0;i < m;i++)
		{
			if (p[i].w != 0)//i为上升子序列起点
			{
				temp = p[i].w;
				sum++;
				for (j = i+1;j < m;j++)
				{
					if (p[j].w >= temp)
					{
						temp = p[j].w;
						p[j].w = 0;
					}
				}
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}