c++ - 为什么此算法的这个 "improvement"不起作用？

Question

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

我们说两个整数 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 block 的 i++ 下添加 j++ 来改进算法，输出从 5(正确的)变为 4。当我在 papper 上测试这个改进时，它似乎有效，但在代码中却无效，为什么？

Answer 1

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

没有添加与 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++ 的 block 中添加 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;
}

[/编辑]