题解：CF2059C Customer Service

· · 题解

有一个显然的性质就是每一个队列只会被恰好操作一次。因为一个队列如果不被操作，它的和至少为 n，但是总共只有 n 个队列，所以 mex 值最大为 n，该队列对答案无贡献。同时，一个队列操作两次和操作一次是等价的，所以你可以用这次操作去修改其他未被操作的队列从而使答案变得更优。

我们接着考虑，一个队列被清空，等价于将这个队列对应那一行行去掉一个前缀，即保留该行的一个后缀。同时，后缀长度为 0,1 \dots n-2,n-1 且互不相同。

接下来考虑如何最大化 mex 值。mex 要求 0 到 i-1 全部存在，且 i 不存在时答案为 i。考虑哪一个队列作为 0，因为队列元素均为正整数，所以只有可能是后缀保留长度为 0 的那一行。同理，作为 1 的队列保留后缀长度为 1，以此类推。

所以，统计每一个队列末尾的 1 的个数并贪心统计答案即可。

代码。