By

文章目录
  1. 1. 题意
  2. 2. 分析

题意

有N堆纸牌，每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若于张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

分析

训练指南上有一种中位数的方法，改了改能过。题解的贪心是从1~n遍历，如果当前的牌少于平均值，就把多余的牌往i+1移动，如果少了的话，就从i+1拿少的那部分牌。
但是这里有一个问题，从i+1那儿拿牌后，如果i+1变成了负数怎么办？解决方法是不用管它，用以后的牌堆来填补这个空缺本来一直不是很明白那个贪心的正确性：

如果当前纸牌不够，那么就要像右边的牌堆借，如果借了右边的所有牌，仍达不到平均值，就要向右边的右边借，以此类推……然而为了保证移动次数最少，相邻的牌堆之间不能有两次同方向的移动，即从i->i+1最多移动一次，若移动两次则一定不是最优。举例：牌堆（1,1,10），显然从10向左移动牌，移动两次即可，而从左向右遍历时，移动次数为3，即（2,0,10）->（2,6,4）->（4,4,4），有两次移动都是从第2堆移动到第1堆，所以不是最优。那么我们从左向右遍历时，怎么满足最优呢？即可以允许借牌时出现负数，比如第1位先从第2位借3个，第2位变成-2，再从第3位借6个，即可求出最优步数。

而为什么能一定可以构造出和变成负数的借牌数相等的方案呢？
my老师告诉我们，考虑：
从1号到n号依次能给就给，不能给的话把不能给的值依次放到一个栈里，把所有欠的牌数都累计起来直到有一堆牌的牌数大于等于所欠的所有牌数清空栈，显然这样的牌堆一定是存在的，所以这个贪心是正确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define MAX 500008
#define ll long long
using namespace std;
stack<int>h;
int main()
{
    int n,a[107];
    while(scanf("%d",&n)!=EOF){
        int sum=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sum/=n;
        int now=0,num=0;
        for(int i=0;i<n-1;i++){
            if(a[i]>=now+sum){
                while(!h.empty()){
                    h.pop();
                }
                now=0;
            }
            if(a[i]>sum){
                a[i+1]+=a[i]-sum;
                a[i]=sum;
                num++;
            }
            else if(a[i]<sum){
                if(a[i+1]>=sum-a[i]){
                    a[i+1]-=sum-a[i];
                    a[i]=sum;
                }
                else{
                    h.push(sum-a[i]);
                    now+=sum-a[i];
                    a[i+1]-=sum-a[i];
                    a[i]=sum;
                }
                num++;
            }
            else{
                continue;
            }
            //printf("%d %d",num,a[i+1]);
        }
        printf("%d\n",num);
    }
}
文章目录
  1. 1. 题意
  2. 2. 分析