| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一次AC 与1065 完全类似。。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator