[二分][DP]BZOJ 2298 HAOI problem a-白红宇的个人博客

[二分][DP]BZOJ 2298 HAOI problem a

发布日期：2021-09-07 21:17:18 浏览次数：3 分类：技术文章

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

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

分析

这题容易想到如果一个人说有a人高过自己，b人低过自己，那么显然从a+1~n-b之间的人分数相等，这就是一段线段。

那么容易想到说假话的人一定线段相交或包含（重合不算）

这个比较难求，我们可以转化一下：求说真话的，显然只有互不相交和重合

所以我们把同样的线段合并，加权（注意权值不能超过线段长度）

然后做DP，设f[i]为做到第i条线段的时候的最大总权。（要给线段排个序）二分求1~i-1的满足r[j]<l[i]的最大f[j]即可

#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=100001;struct Segment {    int l,r;}a[N];int n,cn;int s[N],f[N];bool Cmp(Segment a,Segment b) {    return a.r
           
            
             >1; while (l
             
              >1; if (a[mid].r

View Code

转载于:https://www.cnblogs.com/mastervan/p/9439240.html

转载地址：https://blog.csdn.net/weixin_34304013/article/details/94566244 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：再次用CodeIgniter实现简易blog

下一篇：TRAC-IK机器人运动学求解器

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！