【luogu CF1427F】Boring Card Game(贪心)(性质)

tintown 阅读:59 2023-05-01 21:59:20 评论:0

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$,你需要进行若干次操作,每次操作可以选择一个数 $a_i$,并将其替换为 $a_i-1$ 或 $a_i+1$。你需要使得序列中的所有数都相等,求最少需要进行多少次操作。

$n\leq 10^5$,$|a_i|\leq 10^9$。

解题思路

首先考虑一个简单的问题:给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$,你需要进行若干次操作,每次操作可以选择一个数 $a_i$,并将其替换为 $a_i-1$ 或 $a_i+1$。你需要使得序列中的所有数都相等,求最少需要进行多少次操作。

我们可以发现,对于一个数 $x$,如果我们将所有数都变成 $x$,那么需要的操作次数就是 $\sum_{i=1}^n |a_i-x|$。因此,我们可以枚举 $x$,计算出每个 $x$ 对应的操作次数,取最小值即可。

回到原问题,我们可以发现,如果我们将所有数都变成 $\lfloor\frac{\sum_{i=1}^n a_i}{n}\rfloor$,那么需要的操作次数就是 $\sum_{i=1}^n |a_i-\lfloor\frac{\sum_{i=1}^n a_i}{n}\rfloor|$。因此,我们可以先计算出 $\lfloor\frac{\sum_{i=1}^n a_i}{n}\rfloor$,然后再按照上面的方法计算出最小操作次数。

代码实现


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号