1 #include <bits/stdc++.h>
2 #define _for(i,a,b) for(register int i = (a);i < b;i ++)
3 #define _rep(i,a,b) for(register int i = (a);i > b;i --)
4 #define INF 0x3f3f3f3f
5 #define MOD 100000000
6 #define maxn 150003
7 #define pb push_back
8 typedef long long ll;
9
10 using namespace std;
11 typedef pair<int,int> P;
12 inline ll read()
13 {
14 ll ans = 0;
15 char ch = getchar(), last = ' ';
16 while(!isdigit(ch)) last = ch, ch = getchar();
17 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
18 if(last == '-') ans = -ans;
19 return ans;
20 }
21 inline void write(ll x)
22 {
23 if(x < 0) x = -x, putchar('-');
24 if(x >= 10) write(x / 10);
25 putchar(x % 10 + '0');
26 }
27 struct line
28 {
29 int l;
30 int r;
31 int w;
32 bool operator < (line b)
33 {
34 if(r != b.r)
35 return r < b.r;
36 return l < b.l;
37 }
38 };
39 int N;
40 vector<line> v;
41 map<pair<int,int>,int> m;
42 int dp[maxn];
43 int binarysearch(int l, int r, int val)
44 {
45 while(l <= r)
46 {
47 int mid = (l + r) / 2;
48 if (v[mid].r < val)
49 l = mid + 1;
50 else
51 r = mid - 1;
52 }
53 return r;
54 }
55 int main()
56 {
57 N = read();
58 _for(i,1,N+1)
59 {
60 int a = read();
61 int b = read();
62 if(a+b+1>N) continue;
63 m[{a+1,N-b}] ++;
64 }
65 v.pb({});
66 for(auto p:m)
67 {
68 line tmp;
69 int d = p.first.second-p.first.first+1;
70 tmp.l = p.first.first;
71 tmp.r = p.first.second;
72 tmp.w = min(d,p.second);
73 v.pb(tmp);
74 }
75
76 sort(v.begin(),v.end());
77
78 dp[1] = v[1].w;
79 _for(i,2,v.size())
80 {
81 int nxt = binarysearch(1, i-1, v[i].l);
82 dp[i] = max(dp[i-1], dp[nxt] + v[i].w);
83 }
84 write(N-dp[v.size()-1]);
85 return 0;
86 }
知识兔