【hdoj_1051】WoodenSticks

题目:http://acm.hdu.edu.cn/showPRoblem.php?pid=1051

题意可以理解为：给定若干个二元数对，要将这些数对分为不同的组，同一组中的若干个二元数对可以排列成一个顺序，这个顺序使得二元数对按照两个指标中的任意一个指标都是(不严格)递增的，待求的是，在这种分组方式下，最少可以分多少组.

思路：可以先按照两个指标中的一个指标(长度)给这些二元数对排序，再依次序，根据另一个指标(重量)确定第一组最多可以有多少个二元数对，将这些作为一组，然后以同样的方式考虑剩余的数对.

例如给定(4,9), (5,2), (2,1), (3,5) 和 (1,4).

首先，按照第一个指标排序之后为(1,4),(2,1),(3,5),(4,9)(5,2).记为A,B,C,D,E.

然后，对比第二个指标，A之后的B的第二个指标为B2=1<4=A2不满足.C2=5>4=A2满足，所以C可以与A一组.D2=9>5=C2，所以D可以与A和C一组.E2=2<D2=9，所以E和A不能为一组.第一轮结束，得到A，C和D可以为一组，剩余B和E.

接着，考虑剩余的B和E，E2=2>B2=1，所以E和B可以为一组，没有剩余的了.

所以，这样可以分为两组.

C++代码如下

#include<iostream>#include<algorithm>using namespace std;//木棍 结构体 struct WoodenStick{	int Length;	int Weight;		//构造函数 	WoodenStick(int l=0,int w=0)	{		Length = l;		Weight = w;	}	//设置函数 	void Set(int l=0,int w=0)	{		Length = l;		Weight = w;	}	//< 运算符重载，在排序的时候用到 	bool Operator < (WoodenStick ws)	{		if(Length<ws.Length)			return true;		if(Length == ws.Length)		{			if(Weight<=ws.Weight)				return true;			else return false;		}		else return false;	}};//折半插入排序 void BinSort(WoodenStick ws[],int n){	for(int i=0;i<n;i++)	{		int low = 0,high = i-1,mid;		while(low<=high)		{			mid = (low+high) / 2;			if(ws[i]<ws[mid])					high = mid - 1;			else				low = mid + 1;		}		WoodenStick temp = ws[i];		for(int j=i;j>low;j--)			ws[j] = ws[j-1];		ws[low] = temp;	}}int main(){	int T;	cin >> T;//输入测试数据的组数 	while(T--)	{		int n,Length,Weight;//分别为木棍数目 木棍长度 木棍重量 		cin >> n;		WoodenStick *ws = new WoodenStick[n];  //木棍结构体数组 		for(int i=0;i<n;i++)		{			cin >> Length >> Weight;			ws[i].Set(Length,Weight); //将数据存入木棍结构体数组 		}		BinSort(ws,n);//从小到大排序 				//调试用  查看排序的结果是否正确 		/* 		for(int i=0;i<n;i++)			cout << ws[i].Length << " " << ws[i].Weight << endl;		*/				int result = 0;//每一组测试数据的结果		int * IsOk = new int[n];//是否已经分组分配完毕，即是否可以不再考虑这个二元数对了. 		for(int i=0;i<n;i++) IsOk[i] = 0;//开始都为0，表示所有的二元数对都没有分配完毕 				for(int i=0;i<n;i++)		{			if(!IsOk[i])//针对某个还没有分配的数对 			{				int * IndexOfOk = new int[n];//用于记录，可以和i同为一组的数对的下标 ，以便最后可以让它们一并退出系统 				int NumOfOk = 0;//用于记录，可以和i同为一组的数对的个数 				result ++;//最终结果 				IndexOfOk[NumOfOk++] = i;				for(int j=i+1;j<=n-1;j++)//考察i之后的数对是否可以和i同一组 				{					if(!IsOk[j])//同样是针对没有分配的数对					{						if(ws[IndexOfOk[NumOfOk-1]].Weight<=ws[j].Weight)//可以和前一个同组						{												// (思考前一个为什么不是ws[j-1]) 							IndexOfOk[NumOfOk++] = j;//记录可以同为一组的下标 						}					}				}				for(int k=0;k<NumOfOk;k++)					IsOk[IndexOfOk[k]] = 1;//根据之前记录的下标，让它们逐一退出系统，之后不再(不用)考虑它们了 			}		}		cout << result << endl;	}		return 0;}上述代码提交AC.