Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个容易理解的代码~~AC了的,sort排序+贪心

Posted by goodzhengcheng at 2009-12-03 17:11:32 on Problem 1065
#include<iostream>
#include <algorithm>
using namespace std;
struct zc
{
int l;
int w;
bool selected;
};
bool comp(const zc&a,const zc&b)
{
	if(a.l!=b.l)
		return a.l>b.l;
	else return a.w>b.w;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int time=0;
		int num;
		cin>>num;
		zc * a=new zc[num];
		for(int i=0;i<num;i++)
			a[i].selected=0;
		for(int i=0;i<num;i++)
			cin>>a[i].l>>a[i].w;
		sort(a,a+num,comp);
		for(int i=0;i<num;i++)
		{
			if(!a[i].selected)
			{
				zc temp=a[i];
				for(int j=i+1;j<num;j++)
					if(a[j].l<=temp.l&&a[j].w<=temp.w&&a[j].selected==false)
					{
						a[j].selected=true;
						temp=a[j];
					}
				time++;
			}
			}
			cout<<time<<endl;
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator