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