我们有一个包含 n 个正整数的数组。一个可接受的举措是将所有元素增加 1 或 2 或 5,除了一个元素。我们需要找出使所有数组元素的数量相等的最少操作数。
经过搜索我发现了一种方法:
- 找出非最小元素与最小元素之间的所有差异。
- 通过使用找零硬币的方法,找到找零所需的最少硬币数量。
- 返回所有这些最小硬币数的总和。
但是对于这个测试用例,这种方法失败了:
数组:1,5,5
最小操作数:3 (1,5,5
-> 1,6,6
-> 6,6,11
-> 11,11,11
).
按照上述方法,我得到 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;
}
最佳答案
您发现的方法不适用于由 1、2 和 5 组成的元素集。如您所说,对于 1, 5, 5
,该方法导致 4 次操作(对于“硬币找零”),例如:
1, 5, 5
-> 1, 3, 5
-> 1, 1, 5
-> 1, 1, 3
-> 1, 1, 1
为了均衡所有元素,将除一个元素之外的所有元素增加 1、2 或 5,基本上与将一个元素减少相应的值相同(参见 this 答案)。如果您以这种方式查看您的问题,那么它等于 this问题。
answer对后一个问题的解释是,仅考虑最小元素和非最小元素之间的差异是不够的。您还必须考虑所有元素与最小元素 - 1 和最小元素 - 2 的差异。对于 1, 5, 5
这导致例如以下操作:
1, 5, 5
-> 0, 5, 5
-> 0, 0, 5
-> 0, 0, 0
1, 5, 5
-> -1, 5, 5
-> -1, 0, 5
-> -1, -1, 5
-> -1, -1, 0
-> -1, -1, -1
如您所见,对于您的示例,考虑所有元素与最小元素之间的差异 - 1 给出了使所有元素相等所需的最少操作数,即 3。
您应该调整您的代码以反射(reflect)这种方法。
关于c++ - 使数字列表相等的最小移动次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27728316/