WA on #16!!!!
查看原帖
WA on #16!!!!
1053695
lgx57楼主2024/2/24 19:14
#include<bits/stdc++.h>
using namespace std;
struct node{
	int w,h,id;
}a[5005],b[5005],dp[5005];
int cnt,c[5005],cnt1;
bool cmp(node x,node y){
	if (x.w!=y.w){
		return x.w<y.w;
	}
	return x.h<y.h;
}
bool operator < (const node &x,const node &y){
	return x.h<y.h&&x.w<y.w;
}
bool operator >= (const node &x,const node &y){
	return !(x.h<y.h&&x.w<y.w);
}
bool operator > (const node &x,const node &y){
	return !(x.h<y.h&&x.w<y.w)&&!(x.h==y.h&&x.w==y.w);
}
node min(node x,node y){
	return x<y?x:y;
}
int main(){
	int n,w,h;
	cin>>n>>w>>h;
	for (int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].h;
		if (a[i].w>w&&a[i].h>h){
			b[++cnt].w=a[i].w;
			b[cnt].h=a[i].h;
			b[cnt].id=i;
		}
	}
	if (!cnt){
		cout<<0;
		return 0;
	}
	sort(b+1,b+cnt+1,cmp);
	int tmp=0;
	for (int i=1;i<=n;i++){
		if (dp[tmp]<b[i]){
			dp[++tmp]=b[i];
		}
		else{
			int l=0,r=tmp,mid;
			while (l<r){
				mid=(l+r)/2;
				if (dp[mid]>=b[i]){
					r=mid;
				}
				else{
					l=mid+1;
				}
			}
			dp[l]=min(b[i],dp[l]);
		}
	}
	cout<<tmp<<endl;
	for (int i=1;i<=tmp;i++){
		cout<<dp[i].id<<' ';
	}
	return 0;
}

2024/2/24 19:14
加载中...