1 条题解

  • 0
    @ 2026-1-28 15:18:05
    #include<bits/stdc++.h>
    using namespace std;
    
    // 全局数组:arr存储学校的预计录取分数线,brr存储学生的估分
    int arr[101000], brr[101000];
    
    int main(){
        int m, n; // [1] m:学生人数;n:学校数量
        cin >> n >> m;
        
        // [2] 输入n个学校的预计录取分数线,存入arr数组
        for(int i = 0; i < n; i++) cin >> arr[i];
        
        // [3] 输入m个学生的估分,存入brr数组
        for(int i = 0; i < m; i++) cin >> brr[i];
        
        // [4] 对学校分数线和学生估分分别进行升序排序
        sort(arr, arr + n);
        sort(brr, brr + m);
        
        int sum = 0; // [5] 存储所有学生的最小不满意度之和
        
        // [6] 遍历每个学生的估分,计算其最小不满意度
        for(int i = 0; i < m; i++){
            // 情况1:学生估分 <= 最低的学校分数线
            if(brr[i] <= arr[0])
                sum += arr[0] - brr[i];
            // 情况2:学生估分 >= 最高的学校分数线
            else if(brr[i] >= arr[n-1])
                sum += brr[i] - arr[n-1];
            // 情况3:学生估分在学校分数线的中间范围,用二分查找找最接近的分数线
            else
            {
                int l = 0, r = n;
                // 二分查找:找到第一个大于当前学生估分的学校分数线的位置
                while(l < r)
                {
                    int mid = (l + r) / 2;
                    if(arr[mid] <= brr[i])
                        l = mid + 1;
                    else
                        r = mid;
                }
                // 比较当前位置和前一个位置的分数线,取差值更小的那个
                sum += min(arr[l] - brr[i], brr[i] - arr[l-1]);
            }
        } 
        
        // [7] 输出所有学生的最小不满意度之和
        cout << sum;
        return 0;
    }
    
    • 1

    信息

    ID
    1219
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者