排序后贪心或根据第二关键字找最长下降子序列

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cmath>
#include<climits>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define pb(a) push(a)
#define INF 0x1f1f1f1f
#define lson idx<<1,l,mid
#define rson idx<<1|1,mid+1,r
#define PI 3.1415926535898
template<class T> T min(const T& a,const T& b,const T& c) {
return min(min(a,b),min(a,c));
}
template<class T> T max(const T& a,const T& b,const T& c) {
return max(max(a,b),max(a,c));
}
void debug() {
#ifdef ONLINE_JUDGE
#else freopen("in.txt","r",stdin);
freopen("d:\\out1.txt","w",stdout);
#endif
}
int getch() {
int ch;
while((ch=getchar())!=EOF) {
if(ch!=' '&&ch!='\n')return ch;
}
return EOF;
} const int maxn=;
struct node
{
int l,w;
bool operator < (const node &ant) const
{
return l<ant.l||l==ant.l&&w<ant.w;
}
};
node da[maxn];
int vis[maxn];
int main()
{
int t;
scanf("%d", &t);
for(int ca = ; ca <= t; ca++)
{
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
scanf("%d%d", &da[i].l, &da[i].w);
sort(da, da + n);
memset(vis,,sizeof(vis));
int res=;
for(int cnt=;;)
{
res++;
int curl=-,curw=-;
for(int i=;i<n;i++)
{
if(!vis[i]&&da[i].l>=curl&&da[i].w>=curw)
{
vis[i] = ; cnt++;
curl=da[i].l;curw=da[i].w;
}
}
if(cnt==n)break;
}
printf("%d\n",res);
}
return ;
}

最新文章

  1. Yii2-多表关联的用法示例
  2. 【腾讯Bugly干货分享】安卓单元测试:What, Why and How
  3. codevs4096 删数问题
  4. awk 手册--【转载】
  5. Java之面向对象相关问题集
  6. 要点Java17 String
  7. virtualbox 中安装win7虚拟机
  8. Apache 服务器
  9. MS-SQL 错误: The offset specified in a OFFSET clause may not be negative
  10. ASP.NET Core MVC请求超时设置解决方案
  11. asp.net core使用Swashbuckle.AspNetCore(swagger)生成接口文档
  12. Docker容器跨主机通信
  13. java String转int int转化为String
  14. oralce问题
  15. hdu 4506 快速幂
  16. FPGA中亚稳态相关问题及跨时钟域处理
  17. 在本地SharePoint 2013 搭建App开发环境
  18. 前端 -----02 body标签中相关标签
  19. Sonya and Problem Wihtout a Legend CodeForces - 714E (dp)
  20. react与fetch

热门文章

  1. bzoj3086: Coci2009 dvapravca
  2. SQL Server 2012将数据库备份到网络中的共享文件夹
  3. 简单的Web留言本
  4. JavaScript 在不刷新或跳转页面的情况下改变当前浏览器地址栏上的网址
  5. 鸟哥的linux私房菜学习
  6. java byte转无符号int
  7. [IIS]IIS扫盲(七)
  8. Android UI 绘制过程浅析(三)layout过程
  9. Android如何使用NoHttp
  10. cisco HSRP实验