均衡数字列表的最小移动次数

Question

我们有一个 n 个正整数的数组。可接受的做法是将所有元素增加 1 或 2 或 5，但一个元素除外。我们需要找出最小操作数，以使所有数组元素的数量相等。

经过搜索，我找到了一种方法：

1. 找出非最小元素与最小元素之间的所有差异
2. 通过使用硬币找零方法，找到为所有差异找零所需的最小硬币数量
3. 返回所有这些最小硬币数量的总和

但是这种方法对于此测试用例失败：

数组:< code>1，5，5

最小操作数:3 (1，5，5)

按照上面的方法，我得到了4个。

有人能建议正确的方法吗？

这是我的源代码：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int input[10000];
int input1[10000];
int dp[4][1001];
int parent[4][1001];
int coins[4]={0,1,2,5};
int operation=0;
int main() {
    int t,n,i,j,count,sum,diff,prevdiff,min;
    for(i=1;i<1001;i++)
    {
        dp[0][i]=INT_MAX;
        parent[0][i]=INT_MAX;
    }
    for(i=0;i<4;i++)
    {
        dp[i][0]=0;
        parent[i][0]=-1;
    }
    for(i=1;i<1001;i++){
        for(j=1;j<4;j++){
            dp[j][i]=dp[j-1][i];
            parent[j][i]=parent[j-1][i];
            if(i>=coins[j]&&dp[3][i-coins[j]]<INT_MAX){

                if(dp[3][i-coins[j]]+1<dp[j][i]){
                    dp[j][i]=dp[3][i-coins[j]]+1;
                    parent[j][i]=j;
                }
            }
        }
    }
    cin>>t;
    while(t>0){
        cin>>n;
        min=INT_MAX;
        for(i=0;i<n;i++)
        {
            cin>>input[i];
            if(input[i]<min){
                min=input[i];
            }
            //input1[i]=input[i];
        }

        //sort(input,input+n);

        count=0;
        sum=0;

        for(i=0;i<n;i++){
            count=count+dp[3][input[i]-min];
        }

        cout<<count<<endl;
        t--;
    }
    /*
    for(i=1;i<1001;i++){
        if(dp[3][i]!=minCoins(i))
            cout<<dp[3][i]<<" "<<minCoins(i)<<endl;
    }
    */
    return 0;
}

Answer 1

将除一个数以外的所有数增加1、2或5等于将该数减少1、2和5。因此，这个问题可以转化为另一个问题，其中-

我们希望通过仅使用1次运算来使所有数字相等，即将特定数字减少1,2或5。

为了解决这个问题，我们可以在数组中找到最小的数字。所有数字的最终值将是[min（Array）-4， min（Array）]我们可以遍历所有5个值，对于每个值，我们可以找到使所有元素达到所选值的最小移动次数。最后取我们在每个测试用例中得到的所有5个答案中的最小值。这将是结果。这是我的C代码-

#include<bits/stdc++.h>
using namespace std;

#define int long long int

signed main(){
    int t;
    cin>>t;
    while(t--){
        int n, res = INT_MAX, mini = INT_MAX, ans, temp;
        cin>>n;
        int A[n];
        for(int i=0;i<n;i++){
            cin>>A[i];
            mini = min(mini, A[i]);
        }
        for(int i=mini-4;i<=mini;i++){
            ans = 0;
            for(int j=0;j<n;j++){
                temp = A[j]-i;
                temp = temp/5+(temp%5)/2+(temp%5)%2;
                ans += temp;
            }
            res = min(ans, res);
        }
        cout<<res<<"\n";
    }

    return 0;
}

Answer 2

您发现的方法不适用于由1、2和5组成的元素集。正如您所说，对于1、5、5，该方法会导致4次操作（对于“硬币找零”），例如：

<代码> 1，5，5 -

出于均衡所有元素的目的，将除一个元素之外的所有元素增加1、2或5，本质上与将一个元素减少相应的值相同（见此答案）。如果你这样看待你的问题，那么它等于这个问题。

对后一个问题的回答解释说，仅仅考虑最小要素和非最小要素之间的差异是不够的。您还必须考虑所有元素与最小元素 - 1 和最小元素 - 2 的差异。例如，对于 1、5、5，这将导致以下操作：

<代码> 1，5，5 -

<代码> 1，5，5 -

如您所见，对于您的示例，考虑所有元素和最小元素之间的差异 - 1 给出了均衡所有元素所需的最小操作数，即 3。

您应该调整您的代码，使其反映这种方法。