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

題意可以理解為：給定若干個(gè)二元數(shù)對(duì)，要將這些數(shù)對(duì)分為不同的組，同一組中的若干個(gè)二元數(shù)對(duì)可以排列成一個(gè)順序，這個(gè)順序使得二元數(shù)對(duì)按照兩個(gè)指標(biāo)中的任意一個(gè)指標(biāo)都是(不嚴(yán)格)遞增的，待求的是，在這種分組方式下，最少可以分多少組.

思路：可以先按照兩個(gè)指標(biāo)中的一個(gè)指標(biāo)(長(zhǎng)度)給這些二元數(shù)對(duì)排序，再依次序，根據(jù)另一個(gè)指標(biāo)(重量)確定第一組最多可以有多少個(gè)二元數(shù)對(duì)，將這些作為一組，然后以同樣的方式考慮剩余的數(shù)對(duì).

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

首先，按照第一個(gè)指標(biāo)排序之后為(1,4),(2,1),(3,5),(4,9)(5,2).記為A,B,C,D,E.

然后，對(duì)比第二個(gè)指標(biāo)，A之后的B的第二個(gè)指標(biāo)為B2=1<4=A2不滿足.C2=5>4=A2滿足，所以C可以與A一組.D2=9>5=C2，所以D可以與A和C一組.E2=2<D2=9，所以E和A不能為一組.第一輪結(jié)束，得到A，C和D可以為一組，剩余B和E.

接著，考慮剩余的B和E，E2=2>B2=1，所以E和B可以為一組，沒(méi)有剩余的了.

所以，這樣可以分為兩組.

C++代碼如下

#include<iostream>#include<algorithm>using namespace std;//木棍 結(jié)構(gòu)體 struct WoodenStick{	int Length;	int Weight;		//構(gòu)造函數(shù) 	WoodenStick(int l=0,int w=0)	{		Length = l;		Weight = w;	}	//設(shè)置函數(shù) 	void Set(int l=0,int w=0)	{		Length = l;		Weight = w;	}	//< 運(yùn)算符重載，在排序的時(shí)候用到 	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;//輸入測(cè)試數(shù)據(jù)的組數(shù) 	while(T--)	{		int n,Length,Weight;//分別為木棍數(shù)目 木棍長(zhǎng)度 木棍重量 		cin >> n;		WoodenStick *ws = new WoodenStick[n];  //木棍結(jié)構(gòu)體數(shù)組 		for(int i=0;i<n;i++)		{			cin >> Length >> Weight;			ws[i].Set(Length,Weight); //將數(shù)據(jù)存入木棍結(jié)構(gòu)體數(shù)組 		}		BinSort(ws,n);//從小到大排序 				//調(diào)試用  查看排序的結(jié)果是否正確 		/* 		for(int i=0;i<n;i++)			cout << ws[i].Length << " " << ws[i].Weight << endl;		*/				int result = 0;//每一組測(cè)試數(shù)據(jù)的結(jié)果		int * IsOk = new int[n];//是否已經(jīng)分組分配完畢，即是否可以不再考慮這個(gè)二元數(shù)對(duì)了. 		for(int i=0;i<n;i++) IsOk[i] = 0;//開始都為0，表示所有的二元數(shù)對(duì)都沒(méi)有分配完畢 				for(int i=0;i<n;i++)		{			if(!IsOk[i])//針對(duì)某個(gè)還沒(méi)有分配的數(shù)對(duì) 			{				int * IndexOfOk = new int[n];//用于記錄，可以和i同為一組的數(shù)對(duì)的下標(biāo) ，以便最后可以讓它們一并退出系統(tǒng) 				int NumOfOk = 0;//用于記錄，可以和i同為一組的數(shù)對(duì)的個(gè)數(shù) 				result ++;//最終結(jié)果 				IndexOfOk[NumOfOk++] = i;				for(int j=i+1;j<=n-1;j++)//考察i之后的數(shù)對(duì)是否可以和i同一組 				{					if(!IsOk[j])//同樣是針對(duì)沒(méi)有分配的數(shù)對(duì)					{						if(ws[IndexOfOk[NumOfOk-1]].Weight<=ws[j].Weight)//可以和前一個(gè)同組						{												// (思考前一個(gè)為什么不是ws[j-1]) 							IndexOfOk[NumOfOk++] = j;//記錄可以同為一組的下標(biāo) 						}					}				}				for(int k=0;k<NumOfOk;k++)					IsOk[IndexOfOk[k]] = 1;//根據(jù)之前記錄的下標(biāo)，讓它們逐一退出系統(tǒng)，之后不再(不用)考慮它們了 			}		}		cout << result << endl;	}		return 0;}上述代碼提交AC.