洛谷P1031 均分纸牌

迷南。 2022-05-31 08:28 179阅读 0赞

## 题目描述 ##

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

输出格式：

输出至屏幕。格式为：

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

## 输入输出样例 ##

输入样例\#1： 复制

4
    9 8 17 6

输出样例\#1： 复制

开始没注意看题，写成随便挪动了，结果错了

#include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int heaps[10005];
    
    int cmp(int a, int b)
    {
    	return a > b;
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int N; int aver = 0;
    	cin >> N;
    	for (int i = 0; i < N; i++)
    	{
    		cin >> heaps[i];
    		aver += heaps[i];
    	}
    	aver /= N;
    
    	sort(heaps, heaps + N, cmp);
    
    	int ans = 0;
    
    	for (int i = 0; i < N; i++)
    	{
    		if (heaps[i] == aver)
    			continue;
    		else
    		{
    			ans++;
    			heaps[N - 1] += (heaps[i] - aver);
    			sort(heaps + i + 1, heaps + N, cmp);
    		}
    	}
    	cout << ans;
    	return 0;
    }

看了题解：[https://www.luogu.org/blog/user262/solution-p1031][https_www.luogu.org_blog_user262_solution-p1031]

才发现应该是相邻两堆的相互交换

1.算平均数。

2.求每堆纸牌与平均数的关系（多1记为1，少1记为-1）。

3.当heaps\[y\]（第y堆纸牌与平均数的关系）不等于0时，heaps\[y+1\]=heaps\[y+1\]+heaps\[y\],移动次数加1。

#include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int heaps[10005];
    
    int cmp(int a, int b)
    {
    	return a > b;
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int N; int aver = 0;
    	cin >> N;
    	for (int i = 0; i < N; i++)
    	{
    		cin >> heaps[i];
    		aver += heaps[i];
    	}
    	aver /= N;
    	
    	for (int i = 0; i < N; i++)
    		heaps[i] -= aver;
    
    	int ans = 0;
    	for (int i = 0; i < N; i++)
    	{
    		if (!heaps[i])
    			continue;
    		else
    		{
    			heaps[i + 1] += heaps[i];
    			ans++;
    		}
    	}
    	cout << ans;
    	return 0;
    }

[https_www.luogu.org_blog_user262_solution-p1031]: https://www.luogu.org/blog/user262/solution-p1031