题目描述 如题

思路：

一开始想到的是分治。但是仔细一想，结果是那么回事。
但并不是忠实于题目要求的相邻的两堆牌交换牌，而是跨过已经达到张数的那些牌堆
去做牌的交换了。直接枪毙这种做法。尽管也很有趣。

此种解决方案是一种单纯的模拟。so easy!!!

1）确定当前一堆牌的张数与平均数的大小关系，不等于平均数就要让
   当前的一堆牌达到要求的张数。

2）确定当前一堆牌的位置，只要不是最后一堆，都向它后面的一堆牌交换牌。
   具体的交换牌的规则如下：

   当前一堆牌的位置在首位置到倒数第二的位置的范围时：
   当前一堆牌的数量小于平均数  向后一堆牌借若干张牌
   当前一堆牌的数量大于平均数  向后一堆牌送若干张牌

   当前一堆牌的位置在最后的位置上时：
   当前一堆牌的数量小于平均数  向前一堆牌借若干张牌
   当前一堆牌的数量大于平均数  向前一堆牌送若干张牌

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, m, s;

bool dfs(int u) {
    if(u == n) {
        int claim = 1;
        for(int i = 0; i < n; i++) 
            if(a[i] != m) {
                claim = 0;
                break;
            }
        return claim;
    }

    int* p1  = 0; // p1为当前一堆牌
    int* p2  = 0; // p2为当前一堆牌之前或之后的一堆牌
    if(u == n - 1) p1 = &a[u], p2 = &a[u - 1];
    else p1 = &a[u], p2 = &a[u + 1]; 

    if(*p1 != m) s++;
    *p2 += *p1 - m;
    *p1 = m;

    dfs(u + 1);
    p1 = 0;
    p2 = 0;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        m += a[i];
    }
    m /= n;
    if(dfs(0)) cout << s;
    else puts("No anser");
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, m, s;

bool dfs(int u) {
    // 担心样例无解，所以全部检查一遍，不检查复杂度就成了O(n)
    if(u == n) { 
        int claim = 1;
        for(int i = 0; i < n; i++) 
            if(a[i] != m) {
                claim = 0;
                break;
            }
        return claim;
    }
    int* p1  = 0; // *p1为当前一堆牌
    int* p2  = 0; // *p2为当前一堆牌之前或之后的一堆牌
    if(u == n - 1) p1 = &a[u], p2 = &a[u - 1];
    else p1 = &a[u], p2 = &a[u + 1]; 

    if(*p1 < m) {
        int d = m - *p1;
        *p2 = *p2 - d;  // 借牌
        *p1 = m;
        s++;
    }
    else if(*p1 > m) {
        int d = *p1 - m;
        *p2 = *p2 + d; // 送牌
        *p1 = m;
        s++;
    }
    dfs(u + 1);
    p1 = 0;
    p2 = 0;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        m += a[i];
    }
    m /= n;
    if(dfs(0)) cout << s;
    else puts("No anser")
    return 0;
}

利用前缀和求解。非递归

$$当s[i] != i * \frac{s[n]}{n}时，迭代\sum_{i=1}^n abs(s[i] - i * \frac{s[n]}{n})的次数就是答案 $$

#include <iostream>
using namespace std;
const int N = 110;
int ans, n, a[N], s[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n ; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    if(s[n] % n) puts("No anser");
    else 
        for(int i = 1; i <= n; i++) {
            if(s[i] == i * s[n] / n) continue;
            ans++;
        }
    cout << ans;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int ans, n, m, a[N], s[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n ; i++) {
        cin >> a[i];
        m += a[i];
    }    
    if(m % n) {
        puts("No anser");
        return 0;
    }
    for(int i = 1; i <= n; i++) {
        a[i] -= m / n;
        s[i] = s[i - 1] + a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 0) continue;
        ans++;
    }
    cout << ans;
    return 0;
}