修改 - 题目列表

题意

给定两个长度为 n 的序列：

a_i
b_i

一次操作可以把某个 a_i 加一，花费为与它绑定的 b_i。

但在修改开始前，可以无限次交换任意两个 b。
也就是说，b 最终可以任意重排。

要求把所有 a_i 改成两两不同，并使总花费最小。

思路

先看一个只适合小数据的暴力程序：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

const int MAXN = 12;

int n;
int a_arr[MAXN];
int b_arr[MAXN];
int order_arr[MAXN];
bool used[MAXN];
ull best_ans;

void dfs(int step, int cur_time) {
    if (step > n) {
        int wait_arr[MAXN];
        for (int i = 1; i <= n; i++) {
            wait_arr[i] = order_arr[i];
        }

        sort(wait_arr + 1, wait_arr + n + 1, greater<int>());
        ull cur = 0;
        for (int i = 1; i <= n; i++) {
            cur += (ull)wait_arr[i] * (ull)b_arr[i];
        }
        best_ans = min(best_ans, cur);
        return;
    }

    bool has_avail = false;
    for (int i = 1; i <= n; i++) {
        if (!used[i] && a_arr[i] <= cur_time) {
            has_avail = true;
            used[i] = true;
            order_arr[step] = cur_time - a_arr[i];
            dfs(step + 1, cur_time + 1);
            used[i] = false;
        }
    }

    if (!has_avail) {
        int next_time = INT_MAX;
        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                next_time = min(next_time, a_arr[i]);
            }
        }
        dfs(step, next_time);
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a_arr[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b_arr[i];
    }

    sort(b_arr + 1, b_arr + n + 1);
    best_ans = numeric_limits<ull>::max();
    memset(used, 0, sizeof(used));

    int start_time = a_arr[1];
    for (int i = 2; i <= n; i++) {
        start_time = min(start_time, a_arr[i]);
    }

    dfs(1, start_time);
    cout << best_ans << '\n';
    return 0;
}

暴力版会枚举最终所有互不相同的值，然后算出每个位置需要增加多少，再把这些增量和 b 做最优配对。
它只能用来对拍，但能帮助我们看清结构。

先把问题改写成“调度”

把一个数最终放到某个值 t，就相当于：

它最早只能从 a_i 开始；
如果最后放在 t，就等待了 t-a_i；
这个等待时间乘上绑定的 b_i，就是贡献的代价。

又因为最终所有值必须互不相同，所以每个整数位置最多只能放一个数。
因此题目等价于：

每个 a_i 是一个单位时间作业的最早开始时间；
若作业在时间 t 被安排，就产生等待时间 t-a_i；
最后把等待时间与 b 最优配对。

第二步：固定等待时间后，怎么配 b

设最后得到的等待时间是：

w_i

因为 b 可以任意交换，所以这就变成了一个配对问题：

等待时间大的，应该配费用小的；
等待时间小的，应该配费用大的。

交换论证很直接。
如果有两项满足：

w_x > w_y
b_x > b_y

那么当前配法比交换后多出：

(w_x-w_y)(b_x-b_y) > 0

所以最优配对一定是：

把等待时间降序排序；
把 b 升序排序；
一一配对。

关键：怎样让等待时间本身最优

现在只剩一个问题：

在某个时刻 t，如果已经有多个 a_i <= t 的数可以放，
我们应该先放哪个？

答案是：

先放 a_i 最大的那个。

也就是“出现得最晚，但现在已经可用”的那个数。

为什么？

因为如果两个都能放的数里，一个更晚出现，你却不先放它，那么它以后继续等待只会更亏；
反过来，让更早出现的数多等一会儿，更容易把等待时间集中到一部分数上，后面配 b 时反而更优。

所以整个贪心流程就是：

先把 a 升序排序；
时间从最小 a 开始推进；
用一个大根堆维护所有已经满足 a_i <= 当前时间 的数；
每个时刻取出堆顶，也就是最大的 a_i；
记录等待时间 当前时间-a_i。

用样例 2 体会一下

a = [3,3,4]

如果简单地把它们尽量往前放，等待时间会是：

[0,1,1]

但如果在时间 4 先放 4，再把另一个 3 放到 5，等待时间就变成：

[0,0,2]

后者显然更适合和 b 最优重排，所以总代价更小。
这也正说明，不能只看“每个位置单独尽量小”，而要看等待时间的整体分布。

最终算法

排序 a
排序 b
用大根堆贪心生成等待时间数组 w
把 w 降序排序
计算 sum(w_i * b_i)

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

const int MAXN = 1000005;

int n;
int a_arr[MAXN];
int b_arr[MAXN];
int wait_arr[MAXN];

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx, size;
    char buf[BUFSIZE];

    FastScanner() {
        idx = 0;
        size = 0;
    }

    inline char get_char() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) {
                return 0;
            }
        }
        return buf[idx++];
    }

    template <typename T>
    bool read_int(T &x) {
        char ch = get_char();
        if (ch == 0) {
            return false;
        }

        while (ch != 0 && (ch < '0' || ch > '9')) {
            ch = get_char();
        }
        if (ch == 0) {
            return false;
        }

        x = 0;
        while (ch >= '0' && ch <= '9') {
            x = x * 10 + (ch - '0');
            ch = get_char();
        }
        return true;
    }
} fs;

int main() {
    fs.read_int(n);
    for (int i = 1; i <= n; i++) {
        fs.read_int(a_arr[i]);
    }
    for (int i = 1; i <= n; i++) {
        fs.read_int(b_arr[i]);
    }

    sort(a_arr + 1, a_arr + n + 1);
    sort(b_arr + 1, b_arr + n + 1);

    // 把问题看成“单位时间安排作业”：
    // 每个 a_i 表示这个数最早只能放到位置 a_i；
    // 若它最终放到时间 t，上移次数就是 t-a_i。
    //
    // 为了让后续能把最大的等待时间分给最小的 b，
    // 我们要让等待时间的 multiset 尽量优。
    // 经典贪心是：每个时刻都优先安排当前可选作业里 release time 最大的那个。
    priority_queue<int> pq;
    int i = 1;
    long long cur_time = a_arr[1];
    int tot = 0;

    while (i <= n || !pq.empty()) {
        if (pq.empty() && i <= n && cur_time < a_arr[i]) {
            cur_time = a_arr[i];
        }

        while (i <= n && a_arr[i] <= cur_time) {
            pq.push(a_arr[i]);
            i++;
        }

        int release_time = pq.top();
        pq.pop();
        wait_arr[++tot] = (int)(cur_time - release_time);
        cur_time++;
    }

    // 等待时间越大，越应该配更小的 b。
    sort(wait_arr + 1, wait_arr + n + 1, greater<int>());

    ull ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (ull)wait_arr[i] * (ull)b_arr[i];
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n log n)$
主要来自排序和堆操作。
空间复杂度： $O(n)$

总结

这题最关键的不是“把每个数放到最早位置”，而是：

先把问题看成单位时间调度；
让等待时间的整体分布最优；
再把大等待配给小费用。

一旦完成这一步转化，后面的解法就是很自然的贪心 + 堆。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

测试点	$n$	$a_i$	特殊性质
$1,2$	$\leq10$	$\leq10^9$	无
$3\sim6$	$\leq10^3$	$\leq10^9$	无
$7\sim10$	$\leq10^6$	$\leq10^6$	无
$11\sim14$	$\leq10^6$	$\leq10^9$	所有 $b_i$ 相等
$15\sim20$	$\leq10^6$	$\leq10^9$	无

修改

目录

题意

思路