洛谷-P1031 均分纸牌（贪心）

题目描述

有NN堆纸牌，编号分别为 1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如N=4，4堆纸牌数分别为：

①9②8③17④6

移动33次可达到目的：

从 ③ 取44张牌放到 ④ （9,8,13,10）-> 从 ③ 取33张牌放到 ②（9,11,10,10）-> 从 ② 取11张牌放到①（10,10,10,10）。

输入格式

两行

第一行为：N（N 堆纸牌，1≤N≤100）

第二行为：A_,A_2, … ,A_n （N堆纸牌，每堆纸牌初始数，1≤Ai≤10000）

输出格式

一行：即所有堆均达到相等时的最少移动次数。

输入输出样例

输入 #1

4
9 8 17 6

输出 #1

3

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n;
vector<int> seq(1005);
int average = 0;

int solve()
{
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (seq[i] == average) continue;

        if (seq[i] < average) {
            seq[i + 1] -= average - seq[i];
            seq[i] = average;
        }
        else {
            seq[i + 1] += seq[i] - average;
            seq[i] = average;
        }
        ++cnt;
    }

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i];
        sum += seq[i];
    }
    average = sum / n;

    cout << solve() << endl;

    return 0;
}

贪心类的问题很难说有一个固定的模型，最好是自己举几个例子找找规律，看人为选择怎么去解决，然后用算法去描述这个行为。

这道题很类似开关灯的问题，应该去像一个办法，让后续的结果不影响前面的结果。因为让所有部分都平均，给出的例子，可以认为是17分给6四个，分为8两个，9一个，因为不允许跨越传递，所以可以认为是8的部分暂时帮9的部分存储了。那么用程序来描述，可以认为是打欠条的过程，比如第一个9，自身不够10，那么就向后面一个数借1，并打个欠条，第二个8缺2，本来只需要向17借2，但是手里有个欠条，于是告诉17再多给1个，分给9的直接给8就好了，就可以还清欠条。