「BZOJ2298」[HAOI2011] problem a

2014年12月1日5,2843

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

题解

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

求最多说真话的人数,答案即为n-ans

设dp[i]表示在前i名中最多有多少人说真话

dp[i] = max{dp[j-1]+sum[j][i]} 其中sum[j][i]表示名次区间为[j, i]的人数

 

avatar
3 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
LostMemoryjisefk Recent comment authors
  Subscribe  
提醒
LostMemory
LostMemory

黄学长,这题如果同一个区间的个数超过了区间的长度那么那个区间只能取区间长度次。

jisefk
jisefk

黄学长,请问这题能不用map做吗。。

渠吉超

这是O(2n)的复杂度?
黄学长居然用vector 好偷懒 一直用邻接表。。。