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了的,sort排序+贪心#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator