c++ - k个成对元素之差的最小和

Question

我想计算大小为 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。

Answer 1

我不确定我是否正确理解了您的问题，但它似乎与链接的算法相同，但您可以将值传递给不同 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;;
}