【HAOI2011】problem a

又看题解了，这样下去要跪啊QAQ

原题：

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

1≤n≤100000 0≤ai、bi≤n

想不出来做法，就去看题解了

首先这个题意很有问题，"有ai个人分数比我高"是严格的，有人这么说说明他的排名区间在l=bi+1到r=n-ai之间，且l到r这个区间中所有人的成绩都是一样的

然后有个问题就是如果供词区间在l到r中的人不够r-l+1怎么办？根据鸽巢原理应该可以证明，这样的情况一定会有人说谎，说谎的人填补整下的即可

那么完全相同的区间就可以合并，权值为供词为这个区间的人数，然后求一个线段中不相交的区间覆盖

因为n很大，所以可以用邻接表，先以r第一优先级l第二优先级排序，然后按排好的序扫一下边，如果l[i]和l[i+1]，r[i]和r[i+1]完全相同就不加入链表中，给上一个加入的边权值++，否则链表中插入一条权值为1的边

（其实有更好的实现方式，这个不难想（不是用map= =

最后dp，f[r]=max{f[l-1]+e[i].v} <- 区间覆盖DP

又看题解了，这样下去要跪啊QAQ

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int rd(){int z=,mk=;  char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')mk=-;  ch=getchar();}

     while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-'';  ch=getchar();}

     return z*mk;

 }

 struct dcd{int x,y;}a[];

 struct ddd{int nxt,y,v;}e[];  int lk[],ltp=;

 inline void ist(int x,int y,int z){  e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z;}

 int n;

 int f[];

 bool cmp(dcd x,dcd y){  return (x.y==y.y)?(x.x<y.x):x.y<y.y;}

 int main(){//freopen("ddd.in","r",stdin);

     cin>>n;

     for(int i=;i<=n;++i){

         a[i].x=rd()+,a[i].y=n-rd();

         //if(a[i].x==a[i].y){  cout<<a[i].x<<endl;}

     }

     sort(a+,a+n+,cmp);

     int bwl;

     for(int i=;i<=n;++i){

         bwl=;

         while(a[i+].x==a[i].x && a[i+].y==a[i].y)  ++bwl,++i;

         ist(a[i].y,a[i].x-,min(bwl,a[i].y-a[i].x+));

     }

     for(int i=;i<=n;++i){

         f[i]=f[i-];

         for(int j=lk[i];j;j=e[j].nxt)  f[i]=max(f[i],f[e[j].y]+e[j].v);

     }

     cout<<n-f[n]<<endl;

     return ;

 }

巴特西

【HAOI2011】problem a

最新文章

热门文章