首页 > 代码库 > bzoj2298 [HAOI2011]problem a

bzoj2298 [HAOI2011]problem a

2024-11-26 09:23:01   202人阅读

Description

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

Input

第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi

Output

一个整数，表示最少有几个人说谎

Sample Input

3

2 0

0 2

2 2

Sample Output

1

HINT

100%的数据满足： 1≤n≤100000   0≤ai、bi≤n

 

正解：$dp$+树状数组优化。

对于每一个人，我们可以求出他的分数表示的排名范围：$[1+a,n-b]$。

那么我们可以把最少说慌的人转化成最多说实话的人，如果两个人的区间相交且不重合，那么他们两人必定有一人说谎。如果相同区间的人数超过了区间长度，那么多于区间长度的那些人必定说谎了，也直接去掉就行了。

把重合的区间合并起来，那么我们的问题变成了求带权的最大不相交区间数，这是一个经典的$dp$，可以用树状数组优化。

 

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define N (100010)14 #define il inline15 #define RG register16 #define ll long long17 #define lb(x) (x & -x)18 19 using namespace std;20 21 struct data{ int l,r,v; }q[N],s[N];22 23 int f[N],c[N],n,cnt,ans;24 25 il int gi(){26   RG int x=0,q=1; RG char ch=getchar();27   while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();28   if (ch==‘-‘) q=-1,ch=getchar();29   while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();30   return q*x;31 }32 33 il int cmp(const data &a,const data &b){34   if (a.l==b.l) return a.r<b.r; return a.l<b.l;35 }36 37 il int cmpr(const data &a,const data &b){ return a.r<b.r; }38 39 il void update(RG int x,RG int v){40   for (;x<=n;x+=lb(x)) c[x]=max(c[x],v); return;41 }42 43 il int query(RG int x){44   RG int res=0; for (;x;x-=lb(x)) res=max(res,c[x]); return res;45 }46 47 int main(){48 #ifndef ONLINE_JUDGE49   freopen("a.in","r",stdin);50   freopen("a.out","w",stdout);51 #endif52   n=gi();53   for (RG int i=1,a,b;i<=n;++i) a=gi(),b=gi(),q[i]=(data){1+a,n-b};54   sort(q+1,q+n+1,cmp),q[n+1].l=-1;55   for (RG int i=1,res=1;i<=n;++i){56     if (q[i].l>q[i].r || q[i].l<0 || q[i].r>n){ res=1; continue; }57     if (q[i].l!=q[i+1].l || q[i].r!=q[i+1].r)58       s[++cnt]=(data){q[i].l,q[i].r,min(q[i].r-q[i].l+1,res)},res=1; else ++res;59   }60   sort(s+1,s+cnt+1,cmpr);61   for (RG int i=1;i<=cnt;++i)62     f[s[i].r]=max(f[s[i].r],s[i].v+query(s[i].l-1)),update(s[i].r,f[s[i].r]),ans=max(ans,f[s[i].r]);63   printf("%d\n",n-ans); return 0;64 }

 

bzoj2298 [HAOI2011]problem a


联系
我们