[Codeforces 854.C] Planning

原题

思路

  1. 先考虑简化的问题:如果不要求航班实际起飞时间不早于原定时间,那么如何安排cost最小?
    1. 设第i个航班原计划于$p_i = i$时刻起飞,实际起飞时间是$t_i$,那么总开销 $$C = \sum_i (t_i - p_i)c_i = \sum_i t_i c_i - \sum_i ic_i $$
    2. 显然$\sum_i ic_i$是常数,不予考虑,则只需要使得$\sum_i t_i c_i$最小,即能保证总开销最小。
    3. 由于$(t_1,t_2,\cdots,t_n)$是$(k+1, k+2, \cdots, k+n)$的一个排列,那么由排序不等式(Rearrangement Inequality)可知,逆序和最小。
    4. 故应将$(c_1,c_2,\cdots,c_n)$按降序排序为$(c_{\sigma_1},c_{\sigma_2},\cdots,c_{\sigma_n})$,然后分别安排在$(k+1,k+2,\cdots,k+n)$时刻起飞,即 $$ t_{\sigma_i} = k+i $$
  2. 如果把限制条件($t_i \ge i$)也考虑进来,那么上述逆序和不一定可达。考虑一个具体的例子:

    1
    2
    3
    4
    5
    6
    7
    (ci, i) = (4,1), (2,2), (1,3), (10,4), (2,5)
    # sort by ci
    (ci, i) = (10,4), (4,1), (2,2), (2,5), (1,3)
    # k=2
    ti = 3, 4, 5, 6, 7
    # i.e.
    (i, ti) = (4,3), (1,4), (2,5), (5,6), (3,7)

    (i, ti)即理想的逆序和起飞计划,但此时(4,3)意味着实际起飞时间(3)早于原定起飞时间(4),是不符合条件的,需要进行一定调整。

    1. 只考虑调整方案对$\sum_i t_i c_i $的影响(另一项$\sum_i i c_i$是常数),即实际起飞绝对时间与该航班延误cost的乘积。设需要调整的航班索引为i,按逆序和应将其安排在j时刻起飞,但j < i不满足题意,需将其实际起飞时间安排在时刻m $(m\ge i)$。
    2. 对于给定的调整方案(j -> m),根据排序不等式,应保持所有其他航班起飞顺序不变的基础上依次提前起飞。即计划在(j+1, ... , m)时刻起飞的航班(i+1, ... , i+m-j),调整至(j, ..., m-1)时刻起飞,而航班i于时刻m起飞(循环左移一次)。
    3. 对于给定的m,我们已经得到了最优的调整方案。那么不同的m之间带来的开销增加如何比较?m的最优值是多少呢?
      1. 对于m1,增加的开销 $$\begin{aligned} \Delta(m_1) &= c_i (m_1-j) - \sum_{l=1}^{m_1-j} c_{i+l} \end{aligned}$$
      2. 对于m1 + 1,增加的开销 $$\begin{aligned} \Delta(m_1+1) &= c_i (m_1+1-j) - \sum_{l=1}^{m_1+1-j} c_{i+l} \end{aligned}$$
      3. $$\begin{aligned} \Delta(m_1+1) - \Delta(m_1) = c_i - c_{i+m_1+1-j} \ge 0 \quad (c_i 为降序排序后的序列) \end{aligned}$$
      4. 即增加的开销关于m是递增的,所以m应选取下界i。其实直观上很好理解,延误开销大的飞机尽可能早地起飞。
      5. 另外,由于所有飞机原定起飞时间各不相同,这样调整也不会产生冲突的情况。
  3. 总体来说,需要对$c_i$排序,然后从大到小,将不符合条件的航班安排在原计划时间起飞即可。时间复杂度为$O(n\log n)$。

Code

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
/*
* https://codeforces.com/problemset/problem/854/C
* C. Planning
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
ll val;
int i;
};
/*
* Solution goes here.
*/
pair<ll, vector<int>> planning(int n, int k, vector<Node>& cost) {
sort(cost.begin(), cost.end(), [](auto const& a, auto const& b) {
return a.val > b.val;
});
vector<int> plan(n, 0);
unordered_set<int> arranged;
int now = k + 1;
ll total = 0;
for (int i = 0; i < n; ++i) {
int orig = cost[i].i + 1;
if (now < orig) {
// departure @orig
plan[cost[i].i] = orig;
arranged.insert(orig);
} else {
// departure @now
plan[cost[i].i] = now;
total += cost[i].val * (now - orig);
// find next unscheduled time
while (arranged.find(++now) != arranged.end()) continue;
}
}
return {total, plan};
}