题解 P2519 【[HAOI2011]problem a】

qwaszx · 2019-06-27 15:14:29 · 题解

挺妙的一道题.

设l_i=a_i+1,r_i=n-b_i，那么一个限制等价于第l_i到r_i个人的分数都相等.

然后补集转化成说真话的人最多.对某个人的l,r，如果l>r那么他一定是假的；如果有多于r-l+1个人的l,r都一样那么这些人中最多只能有r-l+1个说真话.

于是问题转化成有n个区间，一个区间[l,r]的权值是\min(r-l+1,\text{区间[l,r]出现的次数}.要求选出尽量多的不相交区间使得权值和最大.

对这个问题我们已经有成熟的解决办法.按r排序，然后设f[i]表示前i个人选若干个的最大权值和，有f[i]=\max\limits_{0\leq j<i,r_j<l_i}\{f[j]\}+w[i]\}.可以二分一个位置然后转移也可以直接对坐标做一个前缀\max.写线段树的不知道是出于什么心理.....

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5;
int n,f[N];
struct Node{int x,y,w;}a[N];
int cmp(const Node &a,const Node &b){return a.y!=b.y?a.y<b.y:a.x<b.x;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),a[i].x++,a[i].y=n-a[i].y;
    sort(a+1,a+n+1,cmp);
    int nn=0;
    for(int i=1,x=0,y=0;i<=n;i++)
    {
        if(a[i].x==x&&a[i].y==y)a[nn].w++;
        else if(a[i].x<=a[i].y)a[++nn]=(Node){a[i].x,a[i].y,1},x=a[i].x,y=a[i].y;
    }
    for(int i=1;i<=nn;i++)a[i].w=min(a[i].w,a[i].y-a[i].x+1);
    int j=1;
    for(int i=1;i<=nn;i++)
    {
        while(j<=a[i].y)f[j]=max(f[j],f[j-1]),++j;//前缀max
        f[a[i].y]=max(f[a[i].y],f[a[i].x-1]+a[i].w);
    }
    cout<<n-f[a[nn].y]<<endl;
}