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 与1065 完全类似。。。

Posted by zihuacs at 2010-08-02 17:25:39 on Problem 1548
#include <iostream>
using namespace std;
struct State
{
	int length;
	int weight;
};
State data[576];
bool isUse[576];
int n;
int ans;
int Comp(const void *a,const void *b)
{
	return (((State *)a)->length != ((State *)b)->length) ? ((State *)a)->length - ((State *)b)->length : 
		((State *)a)->weight - ((State *)b)->weight;
}
// 进行贪心处理
void Greedy_Solve(void)
{
	qsort(data,n,sizeof(State),Comp);
	int i,j,k;

	ans=0;
	for(i=0; i<n; i++)
	{
		if(isUse[i]==false)
		{
			isUse[i]=true;
			ans++;
			k=i;
			for(j=k+1; j<n;j++)
			{
				if(isUse[j])
					continue;
				if(data[k].weight<=data[j].weight)
				{
					isUse[j]=true;
					k=j;
				}
				// 千万不能break 因为涉及两组数据
			}
		}
	}
}
int main(void)
{
	int test_num;
	int r,c;
	int i;
	i=0;
	while(true)
	{
		cin>>r>>c;
		if(r==0 && c==0)
		{
			n=i;
			i=0;
			Greedy_Solve();
			cout<<ans<<endl;
		}
		else if(r==-1 && c==-1)
			break;
		else
		{
			data[i].length=r;
			data[i].weight=c;
			isUse[i]=false;
			i++;
		}
	}
	system("pause");
	return 0;
}

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