K个成对元素之差的最小和
K个成对元素之差的最小和
提问于 2013-10-19 22:42:36
我想计算大小为n和k<=n的数组中k个元素的差的最小和。我所做的是: 1.按升序对元素进行排序2.如果n!=k，则我执行操作3.否则，如果n == k，我执行另一个操作。
例如:n=7 k=3 10 100 300 200 1000 20 30
我将首先对数字进行排序。10 20 30 100 200 300 1000根据我的算法: n!=k，所以首先我将取10 20 30：，这意味着diff = 40继续这样，40是我得到的最小值。
我想知道是否有比这更好的方法：
这是我的算法：
if(n!=k)
{
for(i = 0 ;i < n - k;i++)
{
diff = 0;
l = 0;
for(j = i;j < i + k;j++)
{
diff += (a[j] * l - a[j] *(k-l-1));
if(min < diff)
break;
l++;
}
if(j == i + k && diff > 0)
min = diff;
//cout<<"after: "<<min<<endl;
}
}
else
{
if(k == 1)
min = a[0];
else
{
diff = 0;
for(i = n - 1; i >= 0; i--)
{
diff+=a[i]*i - a[i]*(n-i-1);
}
min = diff;
}
}
cout<<min<<endl;类似于这个问题：Finding sum of Absolute Difference of Every pair of integer from an array
并不是每一对都依赖于k。
回答 1
Stack Overflow用户
发布于 2013-10-20 05:26:32
我不确定我是否正确理解了您的问题，但它看起来与链接的算法相同，但您可以将不同的k值传递给一个函数，该函数将根据传入的k值对向量进行排序。见下文。
#include <vector>
#include <iostream>
#include <algorithm>
int absDiffSum( std::vector<int> v, int k )
{
std::sort(v.begin(), v.begin() + k);
int n=(v.begin() + k) - v.begin();
if ( n < 2 )
return 0;
int sum = 0;
for ( int i = 0; i < n; ++i )
{
int k = n - i - 1;
sum+=(v[i]*i - v[i]*k);
}
return sum;
}
int main ()
{
std::vector<int> v = { 2, 3, 5, 7 };
std::cout << (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) << std::endl;
std::cout << absDiffSum( v, 4 ) << std::endl;;
std::cout << (3-2) + (5-2) + (5-3) << std::endl;
std::cout << absDiffSum( v, 3 ) << std::endl;;
std::cout << (3-2) << std::endl;
std::cout << absDiffSum( v, 2 ) << std::endl;;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19467256
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号