很囧的一道排序加贪心
两个都是N^2的算法......居然这个过了~~~~
囧啊~~
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#define M 20010
using namespace std;
struct doll
{
int w,h;
};
vector<doll>a;
vector<doll>b;
int cmp(const doll a,const doll b)
{
return a.w<b.w||a.w==b.w&&a.h>b.h;
}
int main()
{
// freopen("3636.txt","r",stdin);
int ca;
scanf("%d",&ca);
while(ca--)
{
int n;
scanf("%d",&n);
a.clear();
b.clear();
for(int i=0;i<n;i++)
{
doll d;
scanf("%d%d",&d.w,&d.h);
a.push_back(d);
}
sort(a.begin(),a.end(),cmp);
for(int i=0;i<n;i++)
{
int flag=0;
for(int j=0;j<b.size();j++)
{
if(a[i].w>b[j].w&&a[i].h>b[j].h)
{
b[j].w=a[i].w;
b[j].h=a[i].h;
flag=1;
break;
}
}
if(!flag)
{
b.push_back(a[i]);
}
}
printf("%d\n",b.size());
}
}