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