Skip to content

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;
}