---

8. 摆平积木

原创 于 2023-09-02 21:04:18 发布 · 粉丝可见 · 562 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132642330

题目：

小明很喜欢玩积木。一天，他把许多积木块组成了好多高度不同的堆，每一堆都是一个摞一个的形式。然而此时，他又想把这些积木堆变成高度相同的。但是他很懒，他想移动最少的积木块来实现这一目标， 你能帮助他吗？

输入：

输入包含多组测试样例。每组测试样例包含一个正整数n，表示小明已经堆好的积木堆的个数。 接着下一行是n个正整数，表示每一个积木堆的高度h，每块积木高度为1。其中1<=n<=50,1<=h<=100。 测试数据保证积木总数能被积木堆数整除。 当n=0时，输入结束。

输出：

对于每一组数据，输出将积木堆变成相同高度需要移动的最少积木块的数量。 在每组输出结果的下面都输出一个空行。

样例：

cobol<br/>6<br/>5 2 4 1 7 5<br/>0<br/>

5

题意：

要求最小操作数，使得积木高度相同，换句话来说 给出 a数组，每操作一次 元素 +1 另一个元素 -1。 使得每个元素最后相同，问最小操作数。

思路：

贪心思维模拟题。这里测试数据保证积木总数能被积木堆数整除。所以整除之后的结果是我们需要变成相同高度的最优解，其中要使最小操作数，我们最好分成两个部分进行操作。

分成一个部分是 大于 目标高度的，一个部分是小于该目标高度的。

之后进行贪心操作，贪在，

拿 大于 目标高度中的最小高度的积木 拆解-1 放在 小于目标高度中的最大高度的积木上+1

然后统计每次操作数，就是最小操作数了。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	int n;
	
	// 控制输出格式的换行符
	bool st = false;
	
	while(true)
	{
		scanf("%d",&n);
		
		// n == 0 结束测试
		if(!n) break;
		
		// 输出换行符
		if(st) putchar('\n');
		
		// 目标高度
		int h = 0;
		
		// 每个积木高度
		vector<int>v;
		
		for(int i = 0,x;i < n;++i)
		{
			scanf("%d",&x);
			v.emplace_back(x);
			h += x;
		}
		
		// 求解目标高度
		h /= n;
				
		// 通过优先队列排序好小于目标高度的部分
		// 排序是 由高到低
		priority_queue<int>minH;
		
		// 通过优先队列排序好大于目标高度的部分
		// 排序是 由低到高
		priority_queue<int,vector<int>,greater<int> >maxH;
		
		// 开始遍历分开成两个部分
		for(auto i : v)
		{
			// 如果等于了目标高度，没必要拆分
			if(i == h) continue;
			if(i > h) maxH.push(i);
			if(i < h) minH.push(i);
		}
		
		// 开始模拟最优拆分
		int ans = 0;	// 答案操作数
		
		int maxh = h,minh = h;	// 各部分 取出的积木高度		
		
		while(maxH.size() || minH.size())
		{
			// 如果取出的积木到达了目标高度
			// 我们重新取新的积木
			if(maxh == h)
			{
				maxh = maxH.top();
				maxH.pop();
			}
			if(minh == h)
			{
				minh = minH.top();
				minH.pop();
			}
			
			// 开始拆分
			while(maxh != h && minh != h)
			{
				--maxh;
				++minh;
				++ans;
			}
		}		
		printf("%d\n",ans);
		st = true;
	}
}


int main()
{
//	freopen("a.txt", "r", stdin);
//	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：