poj Wooden sticks

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn = 5010;
class stick{
public:
	int length;
	int weight;
	bool operator < (const stick & item) const
	{
		if(weight == item.weight){
			return length < item.length;
		}
		return weight < item.weight;  //weight优先
	}
}ss[maxn];
int initrecord[maxn];
int main(){
	int t,n,i,j,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i = 0; i < n; ++i){
			scanf("%d%d",&ss[i].length,&ss[i].weight);
		}
		sort(ss,ss+n);
		memset(initrecord,0,sizeof(initrecord));
		int flag = 0;
		int ans = 0;
		for(i = 0; i < n; ++i){
			flag = 0;
			for(j = 0; j <= ans; ++j){
				if(ss[i].length >= initrecord[j]){
					initrecord[j] = ss[i].length;
					flag = 1;
					break;
				}
			}
			if(!flag){
				++ans;
				initrecord[ans] = ss[i].length;
			}
		}
		printf("%d\n",ans+1);
	}
	return 0;
}
           

思路：

首先将木棒按重量优先排序，相同重量按长度优先排序

题目的要求就是找出尽可能少的串，使得每个串中的木棒按长度和重量都不减来排列

由于已经进行了排序，所以按i= 0 ...n-1的顺序枚举，重量一定是不减的，找到一个长度比stick[i]小的木棒，更新这个串中的length值（initrecord[i])

如果没找到，就新开一个串

最后不要忘了加开始的那个1minute