指引 （HG 2018.8.13 T1）

  不会用STL真的是大亏。。虽然我也没想出来怎么贪心。。 首先们看数据范围，横坐标、纵坐标都两两不相同，然后横纵坐标的大小都<2*n，这说明了什么？这说明我们已经不用离散化了，所有的横坐标、纵坐标都是连在一起的！！ 于是，我们可以开一个大小为2*10^5的数组，f[i]记录i这个横坐标是属于人还是属于洞的，h[i]记录这个横坐标所对的纵坐标是多少。 然后，从0~2*10^5我们扫一遍。如果是人的坐标，就把它插进set里，如果是洞的坐标，我们就在插进set里的人的坐标中，找到最后一个纵坐标小于等于这个洞的坐标的人（横坐标已经保证要小了），如果没有这么一个人。。那么说明这个可怜的洞没人走，于是ans不++。有人的话，就把这个纵坐标离洞最近的人走到这个洞，然后ans++，并把这个洞删掉。 找这个人可以用set自带的lower_bound实现。 为什么是对的呢？因为我们从左到右扫，并不用担心set里的人的横坐标比当前扫到的洞的横坐标大，所以，我们尽量满足纵坐标靠近当前洞的人，这样贪心显然是正确的。 代码如下： ```cpp #include<map> #include<set> #include<list> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int read() { int x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } int write(int x) { if(x<0) putchar('-'),x=-x; if(x>=10)write(x/10); putchar(x%10+'0'); } int n; int f[200100],h[200100]; set <int> s; set <int> :: iterator it; int main() { int tmp=read(),ans=0; n=read(); for(int i=1;i<=n;i++) { int x=read(),y=read(); f[x]=1,h[x]=y; } for(int i=1;i<=n;i++) { int x=read(),y=read(); f[x]=0,h[x]=y; } for(int i=0;i<2*n;i++) { if(f[i]) s.insert(h[i]); else { it=s.lower_bound(h[i]); if(it==s.begin()) continue;//没人可以走到当前洞了 ans++; s.erase(--it);//注意，lower_bound找到的是第一个大于等于h[i]的人，所以要--，才是最后一个纵坐标小于等于h[i]的人 } } write(ans); return 0; } ```