1

可能重复：
数组中 3 长度 AP 的最快算法计数

我一直在研究 CodeChef 的 Nov12 挑战中的以下问题。我尝试使用基本公式来检查三个数字 a、b、c 是否在 AP 中，如果 cb=ba 即 2b=a+c，它们是。这是问题所在：

输入的第一行包含一个整数 N (3 ≤ N ≤ 100000)。然后下一行包含 N 个空格分隔的整数 A1、A2、...、AN，它们的值介于 1 和 30000（含）之间。

输出选择三元组的方法数，使得它们是等差数列的三个连续项。例子

输入：

10

3 5 3 6 3 4 10 4 5 2

输出：9

解释：

以下是选择三胞胎的9种方法

1 : (i, j, k) = (1, 3, 5), (Ai, Aj, Ak) = (3, 3, 3)

2 : (i, j, k) = (1, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

3 : (i, j, k) = (1, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)

4 : (i, j, k) = (3, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

5 : (i, j, k) = (3, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)

6 : (i, j, k) = (4, 6, 10), (Ai, Aj, Ak) = (6, 4, 2)

7 : (i, j, k) = (4, 8, 10), (Ai, Aj, Ak) = (6, 4, 2)

8 : (i, j, k) = (5, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

我使用的代码是

#include<stdio.h>
int scan() {
    int p=0;
    char c;
    c=getchar_unlocked();
    while(c<'0' || c>'9')
        c=getchar_unlocked();
    while(c>='0' && c<='9'){
        p=(p<<3)+(p<<1)+c-'0';
        c=getchar_unlocked();
    }
    return(p);
}
int main() {
    int N, i, j, k, count=0;
    N=scan();
    int a[N];
    for(i=0;i<N;i++)
        a[i]=scan();
    for(i=0;i<N-2;i++)
        for(j=i+1;j<N-1;j++)
            for(k=j+1;k<N;k++)
                if(a[k]+a[i]==2*a[j])
                    ++count;
    printf("%d\n", count);
    return 0;
 }

正如您可以看到对变量的约束，很明显我们需要快速高效的算法。为了安全起见，我什至使用了更快的 I/O，但程序仍然超时。很明显，该算法效率不高，因为我使用了三个嵌套循环。另一种减少k's数量的方法是在找到匹配项后立即打破k'循环，然后我会添加一个继续；低于 ++count 并且可以正常工作，但仍然没有问题需要的那么有效。

请告诉我一些快速算法来执行此操作，或者我是否可以在这里学习一些数学定理以更快地找到 AP 三元组。

4

1 回答 1

0

我认为您不需要数组。

从方程中求解 b 2b=a+c，结果为： 

b = (a + c) / 2

使用 4 个变量： a, b, c, and counter.

  1. a, b, c通过读取 3 个值进行初始化。
  2. 如果 (a+c)/2 == b，则递增计数器，并打印 a,b,c。
  3. 移位变量：a = b，b = c。
  4. 而 cin >> c 做：
  5. 如果 (a+c)/2 == b，则递增计数器并打印 a,b,c。
  6. 移位变量：a = b，b = c；
  7. 结束。
  8. 计数器的输出值。

对我来说看起来非常有效。

于 2012-11-10T19:06:00.780 回答