BZOJ2298:[HAOI2011]problem a(DP)-白红宇

BZOJ2298:[HAOI2011]problem a(DP)

阅读量：7101 次

发布时间：2019-06-28

本文共 1170 字，大约阅读时间需要 3 分钟。

Description

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

Input

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

Output

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

Sample Input

2 0

0 2

2 2

Sample Output

HINT

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

Solution

我被打了我是弟弟

问最少多少个人说谎，可以求解最多多少个人说真话。

首先考虑一个人，我们可以得到一个rank的可行区间，然后这个人就可以转化成一条线段。

感性理解一下可以发现线段必须没有交集，也就成了线段覆盖问题。

然而线段还是有权值的。假设有两条条线段$[3,5]$，那么$[3,5]$这条线段的权值就为2，也就是这个线段的出现次数。

可是如果有五条线段$[3,5]$呢？可以发现rank区间$[3,5]$只能容纳三个人，然而有五个人说自己是这个排名，这显然就错了对不对！所以这个时候这个线段的权值是线段的长度。

把所有线段右端点相同的扔到一个vector里面，然后从左到右扫一遍DP就行了。$f[i]$表示到DP到排名$i$，最多有多少个人说真话。

Code

1 #include
      
        2 #include
       
         3 #include
        
           4 #include
          5 #define N (100009) 6 using namespace std; 7  8 int n,x,y,size,f[N]; 9 vector
          
           vec[N];10 map
           
            
             ,int>Map;11 12 int main()13 {14 scanf("%d",&n);15 for (int i=1; i<=n; ++i)16 {17 scanf("%d%d",&x,&y);18 x++; y=n-y;19 int tmp=++Map[make_pair(x,y)];20 if (tmp==1) vec[y].push_back(x);21 }22 for (int i=1; i<=n; ++i)23 {24 f[i]=f[i-1]; size=vec[i].size();25 for (int j=0; j

转载于:https://www.cnblogs.com/refun/p/9789931.html

你可能感兴趣的文章