高考志愿 题解

1
2
3
4
5
6
7
8
9
10
题目描述
现有m<=1e5所学校，每所学校预计分数线是ai<=1e6。有n<=1e5位学生，估分分别为bi<=1e6.

根据n位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式
第一行读入两个整数m,n。m表示学校数，n表示学生数。第二行共有m个数，表示m个学校的预计录取分数。第三行有n个数，表示n个学生的估分成绩。

输出格式
一行，为最小的不满度之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//------------------------------二分------------------------------
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];
int m, n;
int sum;

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    
    sort(a, a + m);
    
    for(int i = 0; i < n; i++){
        int l = 0, r = m - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] >= b[i]) r = mid;
            else l = mid + 1;
        }
        if(b[i] <= a[0]) sum += a[0] - b[i];//特判，当l-1超出边界
        else sum += min(abs(a[l] - b[i]), abs(b[i] - a[l - 1]));
    }
    printf("%d", sum);
    return 0;
}
//---------------------------------STL库函数-----------------------------------
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;
int a[N];
int m, n;
int sum;

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; i++) scanf("%d", &a[i]);
    sort(a, a + m);
    for(int i = 0; i < n; i++){
        int b;
        scanf("%d", &b);
        int d = lower_bound(a, a + m, b) - a;
        if(d == m) sum += b - a[m - 1];//特判范围内所有的数都小于b
        else if(d == 0) sum += a[0] - b;//特判d-1超出范围的情况
        else sum += min (abs(a[d] - b), abs(a[d - 1] - b));
    }
    printf("%d", sum);
    return 0;
}
//-----------------------------贪心----------------------------