https://codeforces.com/contest/1075/problem/C
题意
一个宽为1e9*1e9的矩阵中的左下角，放置一个车（车可以移动到同一行或同一列），放置一些墙，竖的占据一列，横的有一的长度，问车从最下角走到第1e9行最少拆多少面墙？
思路
- 看了看数据范围以为是一道离散化的题，但是发现车可以往左走
- 然后再明确了一下题意，墙是永久拆去的，反应到可以优先拆竖着的墙，然后假如剩下横着的墙比竖着的墙少的话，可以直接拆横着的墙
- 写之前看了一下题意，说横着的墙不会有交点，然后大致确立了贪心策略：
将横着的墙按高度排序，然后一层一层向上爬，更新最右点，假如最右点>p[i].x2,然后就可以向上爬，假如最右点<=p[i].x2,看剩下横着的边多还是竖着的边多，决定是否要更新最右点
- 但是上述思路是错的，因为剩下的横边其实有的不一定要拆
题解
- 首先需要明确两个题意，这对解这道题非常重要
- 横着的边不会有交点，这一点非常重要，因为根据车的性质，假如横着的边有空隙，假设没有竖边，他就一定可以向上走，所以只需要判每条边的左端点是否1，1的边才需要记录，因为车上不去，这样所有的横边就变成了从1开始的边
- 墙是永久拆除的，这样竖着的边就等于一个上界，上界越大，意味着要拆的竖边越多，意味着能通过的横边越多
- 然后就可以枚举竖边（上界），然后找到横边大于上界的点，更新答案（这就是双指针）
#include<bits/stdc++.h>
#define pb push_back
#define M 1e9
using namespace std;
int n,m,i,ans,j,Y,x1,x2;
vector<int>y,x;
int main(){
cin>>n>>m;
for(i=0;i<n;i++){scanf("%d",&Y);y.pb(Y);}
y.pb(M);
for(i=0;i<m;i++){
scanf("%d%d%d",&x1,&x2,&Y);
if(x1==1)x.pb(x2);
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
ans=M;
for(i=0,j=0;i<=n;i++){
while(j<x.size()&&x[j]<y[i])j++;
ans=min(ans,(int)(i+x.size()-j));
}
cout<<ans;
}