首页 > 代码库 > HDU 4341

HDU 4341

二分加贪心,水过了。贪心是因为,不能存在覆盖,当存在覆盖时,留小坐标的。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 300100using namespace std;struct Point{	int left,right;}pl[N];int query[N/3][2];bool cmp(Point a,Point b){	if(a.right<b.right)	return true;	return false;}int find_index(int a,int n){	int l=0; int r=n-1;	int ans=-1;	while(l<=r){		int mid=(l+r)/2;		if(pl[mid].right<=a){			ans=mid;			l=mid+1;		}		else r=mid-1;	}	return ans;}int main(){	int n,m;	while(scanf("%d%d",&n,&m)!=EOF){		for(int i=0;i<n;i++)		scanf("%d%d",&pl[i].left,&pl[i].right);		for(int i=1;i<=m;i++){			scanf("%d%d",&query[i][0],&query[i][1]);		}		sort(pl,pl+n,cmp);		for(int i=1;i<=m;i++){			int a=query[i][0],b=query[i][1];			int bgn=find_index(a,n);			int ans=0;			int pos=a;			for(int k=bgn+1;k<n;k++){				if(pl[k].right<=b){					if(pl[k].left>=pos){						ans++;						pos=pl[k].right;					}				}				else break;			}			printf("%d\n",ans);		}	}	return 0;}

  

HDU 4341