TIOJ 1384 抵抗異形軍

poao899    1548K    686MS    G++     0.66K     2009-11-12 15:24:01                                 .




題目敘述不太好懂Q











二維的LIS










不過二分搜竟然寫炸=口=




//******************

//1384

#include<stdio.h>
#include<algorithm>
struct ship{
	int t,h;
	bool operator<(const ship &b)const{
		return t==b.t?h<b.h:t<b.t;
	}
}S[100050],leng[100050];
int n;
main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",&S[i].t,&S[i].h);
	std::sort(S,S+n);
	int len=0;
	
	for(int i=0;i<n;i++){
		if(S[i].h >= leng[len].h){
			len++;
			leng[len]=S[i];
			continue;
		}
		int l=0,r=len;
		while(l!=r){
			int mid=(l+r)/2;
			if(leng[mid].h <= S[i].h)
				l=mid+1;
			else
				r=mid;
		}
		leng[l]=S[i];
	}
	printf("%d\n",n-len);
}