13016: 【原3016】均分纸牌

题目

题目描述

author: 蔡树阳 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3016

【问题描述】

有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。　　例：若 N=4，4 堆纸牌数分别为：8　7　16　5　　移动3次可达到目的：　　从第三堆取4张牌放到第四堆（8 7 12 9）->从第三堆取3张牌放到第二堆（8 10 9 9）->从第二堆取1张牌放到第一堆（9 9 9 9）。

【输 入】

输入数据包括2行　　第一行是整数N，表示N 堆纸牌（1 <= N <= 100）　　A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）

【输 出】

输出整数M，为所有堆均达到相等时的最少移动次数。

【输入输出样例】

输入  
4
8 7 16 5

输出
3

【数据规模】

100%的数据满足：1<=N<=100  1<=Ai<=10000

FineArtz's solution

/* 均分纸牌 */
#include <iostream>
using namespace std;

int main(){
    int n;
    int a[105] = {0};
    cin >> n;
    int ave = 0;
    for (int i = 0; i < n; ++i){
        cin >> a[i];
        ave += a[i];
    }
    ave /= n;
    int ans = 0;
    for (int i = 0; i < n - 1; ++i){
        if (a[i] < ave){
            ++ans;
            a[i + 1] -= ave - a[i];
            a[i] = ave;
        }
        else if (a[i] > ave){
            ++ans;
            a[i + 1] += a[i] - ave;
            a[i] = ave;
        }
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
using namespace std;

int ai[109] = { 0 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int num;
    cin >> num;
    int average = 0;

    for (int i = 0; i < num; ++i) {
        cin >> ai[i];
        average += ai[i];
    }
    average /= num;

    int ans = 0;
    for (int i = 0; i < num - 1; ++i) {
        if (ai[i] != average) {
            ai[i + 1] -= average - ai[i];
            ai[i] = average;
            ++ans;
        }
    }

    cout << ans;


    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

int main() {
    int data[100];
    int N;
    int sum = 0;
    int cnt = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> data[i];
        sum += data[i];
    }
    sum /= N;
    for (int i = 0; i < N - 1; i++) {
        if (data[i] != sum) {
            data[i + 1] = data[i + 1] + data[i] - sum;
            data[i] = sum;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}