首先对棍子按长度从小到大排序，在长度相等的情况下再按重量由小到

大对棍子排序 

然后从第一跟棍子（长度最小，重量在同长度中最小）开始，

如果该棍子没被使用过 

依次考察后面的没被使用的棍子，如果重量大于等于它的重量，长度大于等于它的长度，则将两跟棍子安排在一个序列中，并将加入序列的棍子置已使用标志。

直到所有棍子都使用完，则序列数即为所需的最小准备时间

#include <iostream>
using namespace std;
int total,n;
int w[5001],l[5001];
int mark[5001];// 标记数组

void sort(int *l,int *w)
{
	int i,j,temp;
	for(i=0;i<n-1;i++)//冒泡排序
	{
		for(j=0;j<n-i-1;j++)
		{
			if(l[j]>l[j+1])
			{
				temp=l[j];
				l[j]=l[j+1];
				l[j+1]=temp;

				temp=w[j];
				w[j]=w[j+1];
				w[j+1]=temp;
			}
			if(l[j]==l[j+1]&&w[j]>w[j+1])//如果长度相等，按质量从小到大排序
			{
				temp=w[j];
				w[j]=w[j+1];
				w[j+1]=temp;
			}
		}
	}
}

void tanxin()
{
	int i,j,temp;
	sort(l,w);
	memset(mark,0,sizeof(mark));
	total=0;
	for(i=0;i<n;i++)
		if(mark[i]==0)
		{
			temp=w[i];
			for(j=i+1;j<n;j++)
			{
				if(w[j]>=temp&&mark[j]==0)
				{
					temp=w[j];
					mark[j]=1;
				}
			}
			total++;
		}
	cout<<total<<endl;
}

int main()
{
	int i,test;
	cin>>test;
	while (test--)
	{
		cin>>n;
		for(i=0;i<n;i++)
			cin>>l[i]>>w[i];
		tanxin();
	}
	return 0;
}

• Re:第一次贪心 解题报告 (23) 181818181818 2009-08-16 16:49:42
• Re:第一次贪心 解题报告 (18) stupidjohn 2010-07-21 19:18:35
• Re:第一次贪心 解题报告 (3) yex 2011-01-29 11:51:10