链接:https://ac.nowcoder.com/acm/contest/1168/H

题目:


题目描述

邓志聪是一位非常聪明的小伙子,这次他在某个学校当班主任,他班上有n个学生,然而有些学生非常的讨厌邓志聪。一次考试结束后,邓志聪想知道这些学生的考试情况,于是一个一个叫这些学生叫去办公室问他们,但是有些学生并没有讲真话,第i个学生说:“有ai个人分数比我高,bi个人分数比我低。”邓志聪想知道最少有几个学生没有说真话,你能帮助他吗?(可能有相同的分数)

输入描述:

第一行一个整数n,接下来每行两个整数,第i+1行两个整数代表ai,bi。(1<=n<=100000,0<=ai,bi<=n)

输出描述:

一个整数,表示最少有几个人在说谎。

输入

3
1 1
2 2
0 2

输出

1

解题思路:


题目要求最少的说谎人数,反向即求最多有多少人没有说谎。

对于第i个学生,由可以确定一个区间(),该区间内的所有学生排名相同,且共有个人。对于一个区间,出现的次数可能大于次,这说有一定有人说谎了,所以最终可以确定一个三元组,,

方法1:

对这些三元组按照R从小到大排序,对于拍完序的第i个元组,在之间二分找到一个最大的j,使得,不断更新答案

方法2:

统计元组中的R对应的所有L,1~n遍历R,枚举R对应的所有L,更新答案

基本思路:确定同排名的人所在的所有区间,寻找一个区间集合满足上一个区间的R<下一个区间的L(目的是得到一个连续的排名),确定区间集合中的最大人数。

ac代码:


方法1:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{
    int l, r, v;
    friend bool operator < (node a, node b)
    {
        return a.r == b.r ? a.l < b.l : a.r < b.r;
    }
}c[maxn];
int n, a, b, L, R;
int f[maxn], p[maxn];
map<pair<int, int>, int> m;
int main() {
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    int num = 1;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &a, &b);
        L = a+1, R = n-b;
        if(L<=R)
        {
            if(m[make_pair(L, R)] == 0)
            {
                c[num].l = L;
                c[num++].r = R;
                m[make_pair(L, R)] = 1;//相同的区间只在c中存储一次
            }
            else m[make_pair(L, R)]++;//统计区间出现的次数
        }
    }
    num--;
    sort(c+1,c+1+num);
    for(int i = 1; i <= num; i++)
    {
        c[i].v = min(m[make_pair(c[i].l,c[i].r)], c[i].r-c[i].l+1);
        p[i] = c[i].r;
    }
    for(int i = 1; i <= num; i++)
    {
        int last = lower_bound(p+1, p+1+num, c[i].l)-p-1;//最后一个小于c[i].l的下标
        //printf("last%d\n", last);
        f[i] = max(f[i-1], f[last]+c[i].v);
    }
    printf("%d\n", n-f[num]);
    return 0;
}

方法2:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{
    int l, r;
}c[maxn];
vector<int> p[maxn];//p[i]中存储(L,R)中R=i的所有L值
int n, a, b, L, R;
int f[maxn];
map<pair<int, int>, int> m;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &a, &b);
        L = a+1, R = n-b;
        if(L<=R)
        {
            m[make_pair(L, R)]++;//统计区间出现的次数
            if(m[make_pair(L,R)] == 1)p[R].push_back(L);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i-1];
        for(int j = 0; j < p[i].size(); j++)
        {
            int cnt = min(i-p[i][j]+1, m[make_pair(p[i][j], i)]);//(L,R)区间出现的次数
            f[i] = max(f[i], f[p[i][j]-1]+cnt);
        }
    }
    printf("%d\n", n-f[n]);
    return 0;
}