均分纸牌问题题解

发表于 更新于 分类于 阅读次数： 评论数：

太久没写C++了，想起来codevs上的题目用来找手感挺好的，做了几道水题。本题目来自于codeVS天梯黄金组，比较简单，使用贪心即可解掉，题目链接：codeVS-1089 。

题目

题目描述

有 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）。

输入描述

第一行N（N 堆纸牌，1 <= N <= 100）
第二行A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）

输出描述

输出至屏幕。格式为：
所有堆均达到相等时的最少移动次数。

样例输入

4
9 8 17 6

样例输出

3

解决思路

  1. 问题的目标函数为使移动次数最少。
  2. 考虑其最终结果必须满足每一个堆的个数都等于平均数。对于规模为$n$下的第一堆，与第二堆进行交换使其满足此条件，则剩下的$n-1$堆为规模为$n-1$情况下的相同问题，满足最优子结构性质。
  3. 同时，对于规模为n的问题，此问题最优解需交换以满足第一堆的牌数等于平均数，则必须经过第一堆与第二堆交换的步骤（假设第一堆不等于平均数，等于时可以减而治之考虑更小规模的问题）。
  4. 假定第二堆牌数可以为负，则第一堆的处理可以在与第二堆的一次交换中实现。假设在问题规模为n时，存在一个最少交换方案即最优方案。同时设包含当前在一次交换中实现第一堆处理的操作同时在从第二堆到第n堆的处理中与最优方案策略相同的方案为方案A。则此最优方案对于第一堆的处理一定给出一个不劣于方案A 的策略，即最多进行一次交换，同时也必须进行一次交换，即此最优方案与方案A具有相同的交换次数，方案A是一个最优方案（满足贪心选择性）。
  5. 此时考虑第二堆牌数不可为负，此时仅需考虑第一堆的个数不足平均数的情形。对于第二堆牌的交换分为向第一堆移动和与第三堆交换两类，此时推迟向第一堆移动的交换到与第三堆交换之后，同时不改变可以为负条件下其他的交换，即可保证第二堆牌数为正，且不改变总交换次数。
  6. 综上，从左到右求解可以为负情形下的问题即可求出最少的交换次数。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# include <iostream>
# include <cstring>
# include <vector>
using namespace std;

#define memset(x) memset(x,0,sizeof(x));


int a[1000];
int n = 0;
int res = 0;
int sum = 0;
int times = 0;


void* divide(int l,int r){
    if(l==r)return NULL;
    if(a[l]>res){
        ++times;
        a[l+1]+=(a[l]-res);
        a[l]=res;
    }else if(a[l]<res){
        a[l+1]-=(res-a[l]);
        a[l]=res;
        times++;
    }
    return divide(l+1,r);
}

int main(){
    cin>>n;
    for(int i = 0;i < n; ++i){
        cin>>a[i];
        sum+=a[i];
    }
    res = sum/n;
    divide(0,n-1);
    cout<<times;
    return 0;
}