1 条题解
-
0
#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
- 上传者