自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 21:21:03，当前版本为作者最后更新于2020-01-21 16:03:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻的第三篇题解，个人认为讲得比较清楚，求赞QwQ~~

废话少说，直接进入正题：

读完题目，我们就应该知道：输出有两种情况，交换次数和 -1.

先考虑输出 -1 （即不能满足题目条件）的情况：

此时有两种可能，总人数（all）大于组数（n）乘上界（r）或小于组数乘下界（l）。代码实现很简单，求出总数再比较,满足条件输出 -1 。

代码如下：

for(int i=1;i<=n;i++)
{
    all+=a[i];
}
if(all<n*l||all>n*r)
{
    cout<<"-1";
    return 0;
}

然后是满足条件的情况：

用 b 数组存不足下限的组一共缺少的人数，用 c 数组存超过上限的组一共超过的人数。

最简单的方法就是用 c 数组中多出的人数去补 b 数组中缺少的人数，但如果 b,c 不相等呢？

当然要使 b,c 都等于0，所以最少交换次数就是 b,c 中较大的数！这道题就做完了！

上代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[51],b,c,all,l,r,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>l>>r;
    for(int i=1;i<=n;i++)
    {
        all+=a[i];
    }
	if(all<n*l||all>n*r)
	{
		cout<<"-1";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]<l)
		{
			b+=(l-a[i]);
		}
		if(a[i]>r) c+=(a[i]-r);
	}
	cout<<max(b,c);
    return 0;
}

大佬勿喷qwq