P9228 原神 做题记录

· · 题解

赛时没有时间写了。回来把题解补上。

点我看题

很套路了。明显是动态规划或者贪心。

考虑贪心。对于 a_i 和 b_j，假如我们只有一个机会使他们进行一次增强（也就是题目里面说的反应规则 2, 3），很明显，我们肯定会选择反应后增加的更多的一个。换言之，假如 a_i > k，我们就会选择 a_i 进行加强。否则选择 b_j。

接下来考虑对于 n, m，我们至多可以选择 \min\{n, m\} 个元素进行增强。加强规则按照上面所述。k 是一个常数，它必然不会变化。因此只需要把 \{a\} 降序排列，从前到后考虑 a_i 就可以了。

初审的时候说要严谨证明。严谨证明没有，这里有个感性理解：

先按照上述规则构造 \{x_i\}, x \in \{a, b\}。证明贪心成立的一个套路就是证明交换后不会更优。假设将 a_i 与 a_j 交换（j < i 且 \{a\} 已经降序排列），那么显然结果不会改变。如果 j > i，那么结果应该变小，\Delta^{-} = (a_i - a_j) \times 2。\{b\} 之间无论如何交换结果仍然不变。

对于 \{a\}, \{b\} 之间的交换，首先会造成原有加强数量减少，其次对于 j > i，还会使增强的值变小。而对于 j < i 仅造成增强数量减小，增强值不变。因此原有贪心是正确的。

为什么要有证明啊，这对数学白痴太不友好了。

最后贴一下核心代码：

signed main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 1; i <= n; i ++ )
        ans += (a[i] = read());
    for (int i = 1; i <= m; i ++ )
        ans += (b[i] = read());
    sort(a + 1, a + n + 1, greater<int>());
    for (int i = 1; i <= n && i <= m; i ++ )
        ans += max(k, a[i]);
    printf("%lld\n", ans);
    return 0;
}