题解 | 撞车最长上升子序列

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define endl '\n'
#define INF 2e18
#define ull unsigned long long
#define pq priority_queue<int>
int mod = 998244353;
const int N = 2e6 + 5;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int days[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

//快速幂
inline int ksm(int a, int b)
{
	int mod = 1000000007;
	int ans = 1;
	a %= mod;
	while (b)
	{
		if (b & 1)ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans % mod;
}

void solve()
{
	int n; cin >> n;
	vector<PII>a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first >> a[i].second;
	}
	vector<int>dp;
	sort(a.begin(), a.end());
	for (auto [st, speed] : a)
	{
		auto it = upper_bound(dp.begin(), dp.end(), speed);
		if (it == dp.end())
			dp.push_back(speed);
		else
			*it = speed;
	}
	cout << n - dp.size() << endl;
}

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

	return 0;
}