CF1859B Olya and Game with Arrays 题解
xiaomuyun
·
·
题解
题意理解
## 思路分析
不难发现：
1. 全部 $\sum\limits_{i=1}^n m_i$ 个数的最小值 $x$ 是一定会被作为某个序列的最小值加入答案的；
2. 对于每个序列的操作肯定是移动最小值。
因此我们可以将每个序列的最小值移动到序列 $i$ 中。那移动到哪个序列呢？
考虑到最终的答案为 $x$ 加上除 $i$ 之外其他序列 **移走最小值之后的最小值**，即 **次小值**。首先我们发现 $x$ 是可以求的定值，其次为了使除了 $i$ 之外其他序列的次小值之和尽可能大，我们不妨让序列 $i$ 为 **次小值最小的那个序列**。然后就非常简单了。
## 代码实现
对于每个序列维护两个数组分别记录最小值和次小值，维护也非常简单，遍历一遍每个数然后判断一下即可。
设遍历到第 $i$ 个序列的数 $v$，且数组 $f_1$ 表示最小值，$f_2$ 表示次小值。则代码如下：
```cpp
if(v<=f1[i]) f2[i]=f1[i],f1[i]=v;
else if(v<f2[i]) f2[i]=v;
```
[AC code](https://codeforces.com/contest/1859/submission/218527219)
无法理解代码的可以私信问我。