1320:[例 6.2] 均分纸牌(Noip2002)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 3537 通过数: 1839
[题目描述]
有 n 堆纸牌, 编号分别为 1,2,..., n. 每堆上有若干张, 但纸牌总数必为 n 的倍数. 可以在任一堆上取若干张纸牌, 然后移动.
移牌规则为: 在编号为 1 的堆上取的纸牌, 只能移到编号为 2 的堆上; 在编号为 n 的堆上取的纸牌, 只能移到编号为 n-1 的堆上; 其他堆上取的纸牌, 可以移到相邻左边或右边的堆上.
现在要求找出一种移动方法, 用最少的移动次数使每堆上纸牌数都一样多.
例如 n=4,4 堆纸牌数分别为: 1 9 2 8 3 17 4 6
移动 3 次可达到目的:
从 3 取 4 张牌放到4(9 8 13 10)->从3取 3 张牌放到 2(9 11 10 10)-> 从2取 1 张牌放到1(10 10 10 10).
[输入]
n(n 堆纸牌, 1 ≤ n ≤ 100)
a1 a2 ... an (n 堆纸牌, 每堆纸牌初始数, l≤ ai ≤10000).
[输出]
所有堆均达到相等时的最少移动次数.
[输入样例]
4 9 8 17 6
[输出样例]
3
例题不怎么详的解:
前辈们告诉我们, OI 的很多题目想要解出来是需要很多奇巧淫技的, 多积累点奇怪的思路和技巧, 不仅对提升成绩有帮助, 还对自己大脑开发有好处(一本正经).
实际上很多 OI 题都要靠奇葩的技巧, 就像其他学科竞赛那样...
这一题也是如此.
很多人一上来看到这题目就直接懵逼了, 没有头绪, 难不成让我用搜索做?
于是乎玄乎的来了, 我们代入一点逆向的思想, 分析输入数据和输出数据的关系, 震惊地发现原来所有牌堆中牌的总数平分到每一个堆中 (即平均值) 就是最后均分的结果, 也照应了题目.
好吧我承认这很容易想出来, 因为题目给出的暗示很明显:
现在要求找出一种移动方法, 用最少的移动次数使每堆上纸牌数都一样多.
好的, 我实力眼瞎没看到, 刚看到这道题我差点就去搜索了... 所以说啊, 认真看题无论在哪里都是第一要素!!!
算法分析:
回到正题, 给出的 n 堆纸牌中, 由于分配不均, 肯定存在牌数最多的一堆, 我们就从这里开始. 经过简单分析, 因为题目只允许将中间牌堆上的牌放到左右两边, 得出以下参考思路:
我们将所有牌的数量除以总堆数的结果称为平均值;
我们将某一堆上牌的总数与平均值之差称为需求值;
找到牌数最多的牌堆, 将牌分成两部分, 一部分的数量是该堆左边每堆牌需求值总和, 另一部分的数量是右边每堆牌需求值总和, 然后分别放置到左右两边.
向左右两边继续执行这样的操作, 由于已经执行过的部分已经达到平均值, 无需改变, 所以这种算法具有无后效性, 只需将最中间的牌向两边摊开就行.
这时我突然意识到一个问题, 如果用这种思路设计算法, 那么代码设计会相对繁琐, 因为要实现规划左右两段的功能, 于是竞赛书上的写法使我虎躯一震, 真的没想到还有这种操作, 果然竞赛靠的还是一个巧.
那就是:
假设一组牌堆, 3 7 17 13, 写成需求值的形式是 - 7 -3 7 3, 我们把 -7 移到 -3 里去, 把 -7 变成 0,-3 变成 -10(相当于 - 3 那一堆挪 7 张牌到 - 7 那一堆, 但是可以在算法中写成此种形式),
-10 再移到 7 里去, 7 变成 -3, 最后把 -3 移到 3 里去, 大功告成.
很明显这种思路比我的思路要来的简单一些, 代码量更少, 那么我就只分析这种算法(其实是我懒).
设置一个关键数组 a, 储存所有牌堆的牌数.
设置一个变量 avg, 储存均值.
设置一个变量 tot, 储存移动总步骤.
我们首先要将需求值计算出来放进一个数组, 我嫌麻烦, 所以将数组 a 再次利用了一次, 将需求值覆盖原数组.
接下来就是算法核心部分的编写, 我们需要遍历一遍数组, 执行上面那个思路:
- for(int t=i;t<j;t++)
- {
- a[t+1]+=a[t];
- a[t]=0;
- tot++;
- }
这就是核心代码, 很简单, 不过有些细节还要处理.
注意: 要 素 察 觉, 如果开头和结尾的牌堆的需求值为 0, 那么此牌堆无需移动. 正确姿势应该是从第一个需求值不为 0 的牌堆移动到最后一个需求值不为 0 的牌堆.
而且, 在移动过程中如果出现恰好前后两牌堆需求值合并得到的值为 0 的情况, 可以跳过一步, 相当于遍历到此牌堆时, 前面的需求值恰好抵消, 等同于已经完成了一轮均分.
因此, 现在需求值为 0 的那个牌堆不需要再移动.
得到如下代码:
- i=0;j=n-1;
- while(a[i]==0&&i<n) i++;
- while(a[j]==0&&j>1) j--;
- for(int t=i;t<j;t++)
- {
- if(a[t]==0) continue;
- a[t+1]+=a[t];
- a[t]=0;
- tot++;
- }
样例代码:
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- using namespace std;
- int main()
- {
- int avg=0,n,a[101],i,tot=0,j;
- scanf("%d",&n);
- for(i=0;i<n;i++)
- {
- scanf("%d",&a[i]);
- avg+=a[i];
- }
- avg/=i;
- for(j=0;j<n;j++) a[j]-=avg;
- i=0;j=n-1;
- while(a[i]==0&&i<n) i++;
- while(a[j]==0&&j>1) j--;
- for(int t=i;t<j;t++)
- {
- if(a[t]==0) continue;
- a[t+1]+=a[t];
- a[t]=0;
- tot++;
- }
- printf("%d",tot);
- return 0;
- }
- 2019-02-08 19:36:03
均分纸牌(Noip2002)
来源: http://www.bubuko.com/infodetail-2947799.html