回 帖 发 新 帖 刷新版面

主题:[讨论]一道ACM道题。高分求解释

有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。
  移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
  现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
  例如 N=4,4 堆纸牌数分别为:
  ① 9 ② 8 ③ 17 ④ 6
  移动3次可达到目的:
  从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。

[输 入]:

  输入文件名a. in。文件格式:
  N(N 堆纸牌,1 <= N <= 100)
  A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000)

[输 出]:

  输出文件名a. out。格式为:
  所有堆均达到相等时的最少移动次数。'

[输入输出样例]

  a. in:
   4
   9 8 17 6 
  a. out:
   3
哪位高手能帮我分析一下吗?

回复列表 (共4个回复)

沙发

贪心就可以。

任何一张牌都只可能往一个方向搬移,不会搬过去又搬回来。

左边n堆牌都排好的情况下,第n+1堆如果比平均数多,则必须往右边挪走多出来的牌(挪1次)。如果少则必须从右边挪来少的牌(即便右边一堆的牌数目不够,可以把它减到负数,由右侧的其他堆来补满)(挪1次)。

当然实际移动的时候需要先补满可能成为负数的堆。如果要求出具体挪动的方法,可以这样:
比如前i个堆已经排好,i+1个堆由i+2个堆挪牌仍然不够,则继续找到j堆牌(j>i+2)
直到i到j这j-i+1堆牌的总数不少于目标值,此时可以从j堆开始往i堆的方向挪牌以补满(注意,这里往回挪的次数也不可能超过j-i次)。完成后继续从j堆往后挪。

板凳

小弟不才,按开大师的方法编了一下,不知对否:
////////////////////////////////////////
#include <iostream>

using namespace std;

int move (int pai[], int n)
{
    int ave, sum = 0;

    for (int i = 0; i < n; ++i)
        sum += pai[i];
    ave = sum/n;
    
    int time = 0, d = 0;

    for (int i = 0; i < n; ++i) {
        d += pai[i] - ave;
        if (d != 0)
            time++;
    }

    return time;
}

int main ()
{
    int pai[4] = {9,8,17,6};

    cout << move (pai, 4) << endl;
    return 0;
}

3 楼

- -|||寒一下

4 楼

如果可以任意移动...?
设小于平均数的堆数为a,大于平均数的堆数为b,任意移动的次数大概是[a,a+b)

我来回复

您尚未登录,请登录后再回复。点此登录或注册