「贪心」均分纸牌

题面链接

均分纸牌

题解

不是太难想到做法的一道贪心题,较简单,证明也不是太难想

读完题目之后首先反应过来的就是,对于每堆牌,我们一定满足的是 每堆纸牌上一定有$Tot = \sum_{i}^{n}A_i / n$这么多张纸牌($A$ 代表初始状态的牌数,$A_i$ 代表初始状态第 $i$ 堆纸牌上的数量,$Tot$ 表示我们每堆牌需要满足的规定的数量)

然后根据题目,我们有以下操作可以改变当前状态不改变当前状态仅表判断

  • 在当前第 $i$ 个牌堆中,此牌堆不满足 $Tot$ 个卡牌,但卡牌数量大于 $Tot$ ,我们将其中 $A_i - Tot$ 个卡牌左移或右移
  • 在当前第 $i$ 个牌堆中,此牌堆不满足 $Tot$ 个卡牌,但卡牌数量小于 $Tot$ ,我们将其中 $Tot - A_i$ 个卡牌从左边或右边移动到该位置
  • 在当前第 $i$ 个牌堆中,此牌堆满足 $Tot$ 个卡牌,我们不对其进行任何操作

对于以上①②两个操作,我们可以再加一些限制防止出现死循环或其他问题 「当前纸堆被遍历过就不能再移动任意纸牌到当前位置」 而且本题目还说了,此牌堆非环状而为线状,那么我们就以进行接下来的考虑了

不考虑答案最优的情况,我们有三种状态可以优先选择

  • 选择第一个牌堆进行操作
  • 选择中间某一个牌堆进行操作
  • 选择最后一个牌堆进行操作

由于我们的新限制左移右移其实可以看成等价移动这两个条件,我们可以只考虑前两个选择而不考虑第三个

对于第一个而言,因为我们只有两种可改变状态的操作,并且我们有一个限制条件,于是我们每次只能选择向右边移动。对于不考虑最优的情况,我们希望每一次操作过后都必须满足遍历过的纸堆都达到 $Tot$ 的值,于是我们得到了一个初步的通向答案的方式

对于第二个而言,因为我们只有两种可改变状态的操作,并且我们有一个限制条件,于是我们只有初状态能选择左移或者右移,接下来的状态就只能选择左移或者只能选择右移。对于不考虑最优的情况,我们希望每一次操作过后都必须满足遍历过的纸堆都达到 $Tot$ 的值,于是我们得到了第二个初步的通向答案的方式

针对这两种方式我们进行讨论,如果当前有 $N = 4$ 堆纸牌,每堆纸牌的数量分别为 $A_1、A_2、A_3、A_4$,并且 $A_i$ 满足 $A_1 ≠ A_2 ≠ A_3 ≠ A_4 ≠ Tot$

对于第一个而言我们很显然可以得到答案 $ans = 3$

对于第二个而言,因为我们选择 $A_2$ 或 $A_3$ 并不会造成结果上大的差异,于是我们随便选一个,选一个$A_2$吧。 然后我们就进行讨论。

  • 当$A_2 > A_1 $且$ A_2 > A_3$且$A_2$不足以支持 $A_1、A_3$ 同时达到 $Tot$

    • 当$A_2$仅能够支持$A_1$达到$Tot$,那么$A_3$就可能需要$A_2$与$A_4$同时给予 此时 $ans = 3$
  • 同理 我们可以得到以下情况

    • $A_2、A_1 > Tot$ 最佳方案是从 $A_1$ 开始向后给予纸牌

    • $A_2、A_3 > Tot$ 最佳方案是从 $A_1$ 开始从左右收取纸牌

    • $A_2、A_4 > Tot$ 和上方同理

于是我们就得到了,在这种情况下,我们不管在任何地方进行操作,都不能再使任何一个成员的情况变得更优,同时又不能使别的成员变得更坏。

于是贪心成立,对于第二个而言,我们可以等同于第一个

于是我们可得代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//#define fre yes

#include <cstdio>

const int MAXN_INT = 105;
int arr[MAXN_INT];

int main() {
static int n, tot, ans;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
tot += arr[i];
} tot /= n;

for (int i = 1; i < n; i++) {
if(arr[i] == tot) continue;
else if(arr[i] >= tot) arr[i + 1] += arr[i] - tot;
else if(arr[i] < tot) arr[i + 1] -= tot - arr[i];
ans++;
} printf("%d\n", ans);
return 0;
}
0%