题解 | 撞车

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

struct car
{
    int x;
    int v;
};

bool cmp(car a,car b)
{
    return a.x<b.x;
}

void solve()
{//根据题意 我们可以很自然的想到 先将每辆车的位置排好 然后再观察他们的速度 如果速度快的在速度慢的后面排着 那么最终肯定会追上
//所以自然想到 一个速度不下降的子序列 是不会存在追尾的 于是为了移除最少的车 我们需要找到最长的不下降子序列
//那么这个时候就成了dp的一道经典模板题 不会的去做一下原题 但注意这道题要用nlogn的最优解做 因为数据量有1e5
    int n;
    cin >> n;
    vector<car>v(n);
    vector<int>ends;
    for(int i=0;i<n;i++) cin >> v[i].x >> v[i].v;
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<n;i++)
    {
        auto it=upper_bound(ends.begin(),ends.end(),v[i].v);
        if(it==ends.end()) ends.push_back(v[i].v);
        else *it=v[i].v;
    }
    cout << n-ends.size();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}