P2519: problem a [HAOI2011]

Problem Description: N students are in classroom, the ith student says there are \(a_i\) students that have scores higher than me and \(b_i\) 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 \(a_i,b_i\)

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 \(a_i\) persons do not affect the result. Secondly, we are trying to maximize the number of students that are not lying. For each given \(a_i\) and \(b_i\), we transform it into a range l = \(a_i\) + 1 and r = N – \(b_i\). 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;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *