点此看题面
大致题意： 一次考试共有
n
n
n个人参加，第
i
i
i个人说有
a
i
a_i
ai个人分数比他高，
b
i
b_i
bi个人分数比他低。求最少有几个人说谎。
动态规划
刚看完题目可以说是一头雾水。
仔细想想，可以把每个人的状态转化为一个区间（
[
a
i
+
1
,
n
−
b
i
]
[a_i+1,n-b_i]
[ai+1,n−bi]），表示这个区间内所有元素都相等。
那么我们要求的就是求出最大的区间数
M
a
x
Max
Max，使这些区间两两之间要么重合，要么不相交，然后用
n
n
n减去
M
a
x
Max
Max即为答案。
考虑将区间左边界排个序，就变成了一个类似于求最长上升子序列的过程，这可以做到
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)。
呃，好像成了一道普及组难度的水题…
代码
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define N 100000
using namespace std
;
int n
,cnt
=0,cnt_
=0,a
[N
+5],f
[N
+5];
struct Interval
{
int l
,r
,v
;
Interval(int x
=0,int y
=0):l(x
),r(y
){v
=1;}
inline friend bool operator < (Interval x
,Interval y
) {return x
.r
^y
.r
?x
.r
<y
.r
:x
.l
<y
.l
;}
inline friend bool operator == (Interval x
,Interval y
) {return !(x
.l
^y
.l
||x
.r
^y
.r
);}
}s
[N
+5];
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f
,FoutSize
,OutputTop
;char ch
,Fin
[Fsize
],*FinNow
,*FinEnd
,Fout
[Fsize
],OutputStack
[Fsize
];
public:
FIO() {FinNow
=FinEnd
=Fin
;}
inline void read(int &x
) {x
=0,f
=1;while(!isdigit(ch
=tc())) f
=ch
^'-'?1:-1;while(x
=ten(x
)+(ch
&15),isdigit(ch
=tc()));x
*=f
;}
inline void read_char(char &x
) {while(isspace(x
=tc()));}
inline void read_string(string
&x
) {x
="";while(isspace(ch
=tc()));while(x
+=ch
,!isspace(ch
=tc())) if(!~ch
) return;}
inline void write(int x
) {if(!x
) return (void)pc('0');if(x
<0) pc('-'),x
=-x
;while(x
) OutputStack
[++OutputTop
]=x
%10+48,x
/=10;while(OutputTop
) pc(OutputStack
[OutputTop
]),--OutputTop
;}
inline void write_char(char x
) {pc(x
);}
inline void write_string(string x
) {register int i
,len
=x
.length();for(i
=0;i
<len
;++i
) pc(x
[i
]);}
inline void end() {fwrite(Fout
,1,FoutSize
,stdout);}
}F
;
inline int find(int x
,int len
)
{
register int l
=0,r
=len
,mid
=l
+r
+1>>1;
for(;l
<r
;mid
=l
+r
+1>>1) a
[mid
]<x
?l
=mid
:r
=mid
-1;
return l
;
}
int main()
{
register int i
,j
,x
,y
,res
,Max
=0;
for(F
.read(n
),i
=1;i
<=n
;++i
) F
.read(x
),F
.read(y
),x
+y
<n
&&(s
[++cnt_
]=Interval(x
+1,n
-y
),0),a
[i
]=INF
;
for(sort(s
+1,s
+cnt_
+1),i
=1;i
<=cnt_
;++i
) cnt
&&s
[cnt
]==s
[i
]?s
[cnt
].v
=min(s
[cnt
].v
+1,s
[cnt
].r
-s
[cnt
].l
+1):s
[++cnt
]=s
[i
];
for(i
=1;i
<=cnt
;++i
)
{
for(res
=find(s
[i
].l
,Max
),j
=res
+1,f
[i
]=res
+s
[i
].v
;j
<=f
[i
];++j
) a
[j
]=min(a
[j
],s
[i
].r
);
Max
=max(Max
,f
[i
]);
}
return F
.write(n
-Max
),F
.end(),0;
}
