题解：P1031 [NOIP 2002 提高组] 均分纸牌

题意

给出

n

，然后给出

n

个数。这

n

个数组成了一个序列（我们不妨将它们设为

a_{1}

到

a_{n}

）。现在可以对这个序列中的每一个数

a_{i}

进行以下三种操作，使得序列中每一个数字都相等：

当 $i$ 为 $1$ 时，可以将 $a_{i}$ 中的一部分移动到 $a_{i+1}$ ，也就是 $a_{2}$ ；
当 $i$ 为 $n$ 时，可以将 $a_{i}$ 中的一部分移动到 $a_{i-1}$ ；
当 $1 < i < n$ 时，可以将 $a_{i}$ 中的一部分移动到 $a_{i+1}$ 或 $a_{i-1}$ 。

显然，这里的“移动”就是使得

a_{i}

减小一个数，使得

a_{i+1}

或

a_{i-1}

加上同一个数。

反过来，

a_{i}

也可以接受其他数的转移。

思路

贪心。

首先，由于要求每个数字相等，那么所有数字的总和一定可以被

n

整除。整除后的这个数字（也是这个序列的平均数），我们暂且把它叫做

num

。

此时，对于序列中的每一个数

a_{i}

，只有三种情况：

如果 $a_{i} > num$ ，则 $a_{i}$ 多出来的部分（ $a_{i} - num$ ）应该被转移到临近的数上；
如果 $a_{i} < num$ ，则 $a_{i}$ 缺少的部分（ $num - a_{i}$ ）应该由邻近的数转移而来；
如果 $a_{i} = num$ ，则不需要进行任何操作。

那么，这个“临近的数”，应该是哪一侧的数呢？

让我们回到这个序列上。

对于

a_{1}

，因为它左侧没有数，所以它进行的一切操作都只能依靠

a_2

。而当我们对它进行了操作后，

a_{1}

显然就和

num

相等了。

这时，对于

a_{2}

，因为它左侧的

a_{1}

已经与

num

相等了，所以它进行的一切操作都只能依靠

a_{3}

。而当我们对它进行了操作后，

a_{2}

显然就和

num

相等了。

以此类推，我们就解决了刚才的问题：对于

a_{i}

，因为它左侧的

a_{i-1}

已经与

num

相等了，所以它进行的一切操作都只能依靠

a_{i+1}

。而当我们对它进行了操作后，

a_{i}

显然就和

num

相等了。

所以，对于序列中的每一个数

a_{i}

，变成了这三种情况：

如果 $a_{i} > num$ ，则 $a_{i+1} = a_{i+1} + a_{i} - num$ ， $a_{i} = num$ ；
如果 $a_{i} < num$ ，则 $a_{i+1} = a_{i+1} - num + a_{i}$ ， $a_{i} = num$ ；
如果 $a_{i} = num$ ，则不需要进行任何操作。

对于前两种情况，不难发现，其实它们进行的操作是一样的。

CPP

for(ll i=1;i<n;i++){
	if(a[i]==num) continue;//相等则不进行操作
	a[i+1]+=(a[i]-num);//否则进行移动
	a[i]=num;
	ans++;//答案增加
}

代码实现

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans,a[110],num;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		num+=a[i];//求序列和
	}num/=n;//求平均数
	for(ll i=1;i<n;i++){
		if(a[i]==num) continue;//相等则不进行操作
		a[i+1]+=(a[i]-num);//否则进行移动
		a[i]=num;
		ans++;//答案增加
	}cout<<ans;
	return 0;//好习惯
}//完结撒花QAQ

题解：P1031 [NOIP 2002 提高组] 均分纸牌

文章操作

题解：P1031 [NOIP 2002 提高组] 均分纸牌

题意

思路

代码实现

相关推荐

评论

题解：P1031 [NOIP 2002 提高组] 均分纸牌