| ||||||||||
| 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