时间戳

首页 > 解决方案 > 为什么这种算法的“改进”不起作用？

c++ - 为什么这种算法的“改进”不起作用？

问题描述

我创建了一个算法来解决以下问题陈述：问题陈述是：

我们说两个整数 x 和 y 至少有 K 的变化，如果 |x - y| ≥K（它们的差值绝对值至少为K）。给定一个由 N 个整数 a1,a2,...,aN 和 K 组成的序列，总变异数是序列中变异至少为 K 的元素对的数量，即它是对集合的大小

{(i,j)|1≤i<j≤N and|ai−aj|≥K}

代码：

int n, k, count = 0;
cin >> n >> k;

int v[n];

for (int i = 0; i < n; i++) {
    cin >> v[i];
}

sort(v, v + n);

for (int i = 0, j = 1; i < n;) {

    if (abs(v[i] - v[j]) >= k) {
        count += (n-j);
        i++;
    }
    else
        j++;
}
cout << count;
return 0; }

如果我们有输入：

4 1 // first int is the number of N integers, the second int is the k.
3 1 3 2 // first integers.

所以我的问题如下：如果我想通过在 if 块中的 i++ 下添加 j++ 来改进算法，输出会从 5（正确的）变为 4。当我在 papper 上测试这种改进时，它似乎工作，但在代码中却没有，为什么？

标签： c++algorithm

解决方案

如果我用你的输入跟踪执行

没有添加与 i++ 关联的 j++ ：

(abs(v[0] - v[1]) >= k) = 1
    count += (n-1)
(abs(v[1] - v[1]) >= k) = 0
(abs(v[1] - v[2]) >= k) = 1
    count += (n-2)
(abs(v[2] - v[2]) >= k) = 0
(abs(v[2] - v[3]) >= k) = 0
(abs(v[2] - v[4]) >= k) = 1
    count += (n-4)
(abs(v[3] - v[4]) >= k) = 1
    count += (n-4)
result 5

如果我在包含 i++ 的块中添加 j++ ：

(abs(v[0] - v[1]) >= k) = 1
    count += (n-1)
(abs(v[1] - v[2]) >= k) = 1
    count += (n-2)
(abs(v[2] - v[3]) >= k) = 0
(abs(v[2] - v[4]) >= k) = 1
    count += (n-4)
(abs(v[3] - v[5]) >= k) = 1
    count += (n-5)

result 4

这不是一回事，在那种情况下，结果不一样是因为最后一个count += (n-5)而不是count += (n-4)因为 j 的值

[编辑添加]

测试程序：

#include <iostream>
using namespace std;

int main(int, char **)
{
#if 0
  int n, k, count = 0;
  cin >> n >> k;

  int v[n];

  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  sort(v, v + n);
#else
  int n = 4, k = 1;
  int v[] = { 1, 2, 3, 3};
  int count = 0;
#endif

  for (int i = 0, j = 1; i < n;) {
    cout << "(abs(v[" << i << "] - v[" << j << "]) >= k) = " << (abs(v[i] - v[j]) >= k) << endl;
    if (abs(v[i] - v[j]) >= k) {
      cout << "\tcount += (n-" << j << ")" << endl;
      count += (n-j);
      j++;  // THIS LINE IS IN COMMENT OR OUT OF COMMENT
      i++;
    }
    else
      j++;
  }
  cout << count;
  return 0;
}

[/编辑]

推荐阅读