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

考试

时间限制: 1 Sec 内存限制: 128 MB

题目描述

S中开展了省选集训，有n位选手的实力参差不齐。众所周知，如果题目太水，那么就会有人AK离场后打游戏，如果题目太难，那么就会有人颓废离场后打游戏。作为出题人的你自然不希望有太多人出去打游戏，不然ob就会很生气。所以你需要设定题目的难度，尽量让最少的人出去打游戏，并且同时题目尽可能难一些。 输入 第1行一个正整数n，表示一共有n名选手参与； 接下来n行两个非负整数Ai,Bi，表示第i位选手可接受的题目难度范围在Ai~Bi之间，若你设定的题目难度超过此区间，这位选手便会离场打游戏。

输出

一共一行一个数字ans，表示你设定的题目难度为ans，应当在让最少的人离场的同时使其尽可能的大。 样例输入 Copy 3 1 5 95 105 5 110 样例输出 Copy 105 提示 样例解释 有三名选手参与，方便起见命名第1名选手叫小X，第2名选手叫小Q，第3名选手叫小P。 题目难度如果要满足蒟蒻小X，那么小Q便一定会AK后颓废，为了兼顾小P，难度不得不设为5，此时1人离场。 如果要满足巨佬小Q，那么无论如何小X也会觉得题目太难愤愤离场，为了兼顾小P，难度最大可设为105,此时1人离场。 综上，题目难度最大为105。 【数据范围】 对于30%的数据：n ≤ 10 对于50%的数据：n ≤ 1000 对于另外20%的数据： 0 ≤ Ai ≤ Bi ≤ 100000 对于100%的数据： n ≤ 100000， 0 ≤ Ai, Bi ≤ 1000000000

题意就是给出每个人能承受难度的范围，超过这个范围这个人就会离场，在最少离场人数中找一个最大的难度。也就是找一个点，这个点被覆盖的次数最多且尽可能大，且这个点最优解一定是在端点上的，可以证明对于每一个不在端点上的点， 一定可以找到一个在端点上的点来替代。对于每一名选手，在承受范围 [l,r] 区间上加一，代表这个区间内每一个难度都多一位同学可以比赛，寻找数最大的端点即可。在区间加数不难想到差分，但是这个题 l 和 r 的范围比较大，需要离散化处理一下即可。

题目跟队爷的新书挺像的，应该还可以用扫描线水掉。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

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