学生和导师

题目 学生和导师

思路分析

一对多的师生关系 同一个老师可以被多次选

所以只要对每个学生二分找到最大的那个\(<2*a[i]\)的学生即可

排序一下就有二段性了

（很常用的技巧 没有二段性 自己构造二段性 前面单调栈也可以 简单排序也可以）

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1e6+10;
int a[N],s[N];
int T,n;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        for(int i=1;i<=n;i++)   cin>>a[i];
        //二分查找用s（要求有序） 遍历用a（需要知道当前找到是哪个学生）
        memcpy(s,a,sizeof a);
        sort(s+1,s+1+n);
        cout<<"Case #"<<t<<": ";
        for(int i=1;i<=n;i++){
            //对每个a[i]，二分找到最后一个<=2*a[i]的数 即区间划为左满足右不满足
            int l=1,r=n;
            while(l<r){
                int mid=l+r+1>>1;
                if(s[mid]<=2*a[i])  l=mid;
                else    r=mid-1;
            }
            //int r=upper_bound(s+1,s+n+1,2*a[i])-s-1;

            //如果最后找到的答案不在(a[i],2a[i]]的话（超范围了或者找到自己了） 往左挪（答案一定在左边）
            if(s[r]>2*a[i] || s[r]==a[i])
                r--;
            //二分找到0 即r等于0表示对于a[i]没有数符合题意
            if(r)
                cout<<s[r]<<" ";
            else
                cout<<"-1 ";//忘打空格 Presentation Error（演示错误）
        }
        cout<<endl;
    }
    return 0;
}

同类题型

视频讲解

⬅️ 卡牌 🏠 00-刷题理模型 ➡️ 小蓝与捉迷藏