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

【题解】

题意：n个学生分别拥有歌唱能力xi和说相声能力yi，每个人都必须选一个参加，节目的效果等于参加学生中这个才艺最大的能力值，最小化两个界节目的效果差值并输出这个值。

思路：按xi降序排序，从大到小枚举每个值作为歌唱界面的最大值，那么x大于当前值的学生必然要选择说相声，所以我们可以用b记录一定要说相声的能力最大值，那么x小于当前值的学生只有y大于b才有影响答案的可能。我们可以用一个multiset维护当前可选的y值，如果最大的y值都小于a(当前x值)，当然前提是大于b，那么答案显然为a-可选最大y值；否则二分寻找大于等于a的y值，更新最优答案，如果这个y值不是最小可选的值那么要判断上一个y值是否能影响答案。

【代码】

#include 
   
    using namespace std;const int maxn=1e5+10;#define ll long longstruct p{    ll x,y;}f[maxn];bool cmp(p a,p b){return a.x>b.x;}multiset 
    
      se;multiset 
     
       ::iterator it;int main(){    int T; scanf("%d",&T);    while(T--){        se.clear();        int n; scanf("%d",&n);        for(int i=0;i
      
       b){                    if(*it
       
        b) ans=min(ans,abs(a-*it));                    }                }            }            b=max(b,f[i].y);        }        printf("%lld\n",ans);    }    return  0;}
       
      
     
    
   

转载地址：http://gqfen.baihongyu.com/