P2519: problem a [HAOI2011]

Problem Description: N students are in classroom, the ith student says there are students that have scores higher than me and students that have scores lower than me(There might exist same scores). Please give out the minimum possible number of students that are lying.

Input Format:
First line with one integer N ≤ 100000
Next N lines with two integers denoting

Output Format:
One line with the minimum possible number of lying students.

Sample Input:
3
2 0
0 2
2 2

Sample Output:
1

Solution: This is one DP problem. First, we notice that which persons do not affect the result. Secondly, we are trying to maximize the number of students that are not lying. For each given and , we transform it into a range l = + 1 and r = N – . If l > r, it is obviously wrong. If r – l + 1 is less than the number of persons who claimed they are in this range, then the part that exceeds r – l + 1 is false. We say for each range [l,r], there is a weight equals to the maximum number of people who can be in this range. We have following DP formula:
$$f[i] = \max(f[i – 1],f[k] + V_i)$$, where f[i] denotes the maximum people that can be in the first i ranges and 1 ≤ k ≤ i – 1. Then the answer equals to N – f[m].

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
#define inf 0x7f7f7f7f
const int maxn = 100005;
int N,f[maxn];
struct node{
    int l,r,v;
    node(int a = 0,int b = 0,int c = 0):l(a),r(b),v(c){};
} a[maxn],b[maxn];
bool cmp1(node a,node b){
    if(a.l != b.l) return a.l < b.l;
    return a.r < b.r;
}
bool cmp2(node a,node b){
    if(a.r != b.r) return a.r < b.r;
    return a.l < b.l;
}
int bin_search(int l,int r,int x){
    while(l <= r){
        int mid = (l + r) >> 1;
        if(a[mid].r < x) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
int main(){
    FAST_IO
    cin>>N;
    for(int i = 1; i <= N; i++){
        cin>>a[i].l>>a[i].r;
        a[i].l++;
        a[i].r = N - a[i].r;
    }
    sort(a + 1, a + 1 + N,cmp1);
    int cnt1 = 0,cnt2 = 0;
    for(int i = 1; i <= N; i++) if(a[i].l <= a[i].r) b[++cnt1] = a[i];
    for(int i = 1; i <= cnt1; i++){
        if(b[i].l != b[i - 1].l || b[i].r != b[i - 1].r){
            a[++cnt2] = b[i];
            a[cnt2].v = 1;
        } 
        else{
            a[cnt2].v++;
            a[cnt2].v = min(a[cnt2].v,a[cnt2].r - a[cnt2].l + 1);
        }
    }
    sort(a + 1,a + 1 + cnt2,cmp2);
    f[1] = a[1].v;
    for(int i = 2; i <= cnt2; i++){
        int k = bin_search(1,i-1,a[i].l);
        f[i] = max(f[i - 1],f[k] + a[i].v);
    }
    cout<<N - f[cnt2]<<endl;
    return 0;
}