P1031 均分纸牌

    • 10.7K通过
    • 19.1K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 概率论,统计 模拟 贪心 NOIp提高组 2002
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有 $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 \le N \le 100$ )

    第二行为: $A_1,A_2, … ,A_n$ ( $N$ 堆纸牌,每堆纸牌初始数, $l \le A_i \le 10000$ )

    输出格式:

    一行:即所有堆均达到相等时的最少移动次数。

    输入输出样例

    输入样例#1: 复制
    4
    9 8 17 6
    
    输出样例#1: 复制
    3
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。