学生分组

题意

给定 n 个组当前的人数，以及每组允许的人数范围 [L,R]。
每次操作可以把某一组里的一个学生移动到另一组。
要求最少经过多少次操作，才能让所有组的人数都落在 [L,R] 中；如果做不到，输出 -1。

思路

先看一个可以直接验证想法的朴素解：

枚举每个组最终应该有多少人，只要这些目标人数都在 [L,R] 中且总人数不变，就能算出实现这个目标分配至少要几次转移。

cpp

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
61
62
63// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int INF = 1e9;

int n;
int a[MAXN];
int l, r;
int best;

void dfs(int idx, int left_sum, int moved_out) {
    if (idx > n) {
        if (left_sum == 0) {
            best = min(best, moved_out);
        }
        return;
    }

    int remain = n - idx;
    for (int v = l; v <= r; v++) {
        int rest = left_sum - v;
        if (rest < 0) {
            continue;
        }
        if (rest < remain * l || rest > remain * r) {
            continue;
        }
        dfs(idx + 1, rest, moved_out + max(0, a[idx] - v));
    }
}

void solve() {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
    }

    if (sum < n * l || sum > n * r) {
        cout << -1 << '\n';
        return;
    }

    best = INF;
    dfs(1, sum, 0);
    cout << best << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> l >> r;

    solve();

    return 0;
}

这个办法可以帮助理解，但没有必要真的枚举最终分配。

我们只需要关心两种组：

人数小于 L 的组：它们至少需要补进一些学生
人数大于 R 的组：它们至少需要挪出一些学生

记：

need_in：所有缺人组总共至少缺多少人
need_out：所有超额组总共至少要送出多少人

如果总人数本身都不在 [nL, nR] 内，那一定无解，直接输出 -1。

如果总人数合法，那么一次操作可以同时完成两件事：

某组少 1 人
另一组多 1 人

因此最少操作次数一定不少于 need_in 和 need_out，同时也总能在 max(need_in, need_out) 次内完成调整。
所以答案就是：

max(need_in, need_out)

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;

int n;
int a[MAXN];
int l, r;

void solve() {
    int sum = 0;
    int need_in = 0;   // 不足下界的组，总共至少需要补进多少人
    int need_out = 0;  // 超过上界的组，总共至少需要挪出多少人

    for (int i = 1; i <= n; i++) {
        sum += a[i];
        if (a[i] < l) {
            need_in += l - a[i];
        }
        else if (a[i] > r) {
            need_out += a[i] - r;
        }
    }

    if (sum < n * l || sum > n * r) {
        cout << -1 << '\n';
        return;
    }

    cout << max(need_in, need_out) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> l >> r;

    solve();

    return 0;
}

复杂度

时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$ 。

总结

这题的关键不在模拟移动过程，而在于直接统计“总缺口”和“总超额”。

只要总人数可行，答案就可以直接写成 max(缺口, 超额)。

目录

题意

思路

代码

复杂度

总结