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

liu鲤鱼 · 2025-02-22 19:26:12 · 题解

题解：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，则不需要进行任何操作。

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

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

代码实现

#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