有效的方法来查找数字在A.P.中的所有这些三元组的数量（来自给定的一组数字）？ [重复]

Possible Duplicate:
fastest algorithm count number of 3 length AP in array

可能重复:阵列中3个长度AP的最快算法计数

I've been working on the following problem taken from CodeChef's Nov12 challenge. I tried it using the basic formula for checking whether three numbers a, b, c are in A.P., they are if c-b=b-a i.e. 2b=a+c. Here is the problem:

我一直在研究从CodeChef的Nov12挑战中获得的以下问题。我尝试使用基本公式检查三个数字a,b,c是否在A.P.中,如果c-b = b-a,即2b = a + c。这是问题所在:

First line of the input contains an integer N (3 ≤ N ≤ 100000). Then the following line contains N space separated integers A1, A2, …, AN and they have values between 1 and 30000 (inclusive).

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

Output the number of ways to choose a triplet such that they are three consecutive terms of an arithmetic progression. Example

输出选择三元组的方式的数量,使得它们是算术级数的三个连续项。例

Input:

3 5 3 6 3 4 10 4 5 2

Output: 9

Explanation:

The followings are all 9 ways to choose a triplet

以下是选择三联体的所有9种方法

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

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)

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)

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)

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)

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)

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)

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)

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

The code I used is

我使用的代码是

#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;
 }

As you can see the constraints on variables, it is clear that we need fast and efficient algo. For the sake of safety I even used faster I/O but still the program runs out of time. It is clear that the algorithm is not that efficient, as I am using three nested loops. One other way that come to reduce the number of some k's is to break the k' loop as soon as a match is found, then I would have added a continue; below ++count and that is working but again NOT that efficient as the problem requires.

正如您可以看到变量的约束,很明显我们需要快速有效的算法。为了安全起见,我甚至使用了更快的I / O,但程序仍然用完了。很明显,算法效率不高,因为我使用了三个嵌套循环。另一种减少某些k的数量的方法是在找到匹配后立即打破k'循环,然后我会添加一个继续;低于++计数,这是有效的,但不是那么有效,因为问题需要。

Please tell me some fast algo to do this, or if I might learn some mathematical theorem here to find AP triplets quicker.

请告诉我一些快速算法,或者如果我可以在这里学习一些数学定理以更快地找到AP三元组。

1 个解决方案

#1

I don't think you need an array.

我认为你不需要阵列。

Solve for b from your equation 2b=a+c, and the result is:

从等式2b = a + c求解b,结果为:

b = (a + c) / 2

Use 4 variables: a, b, c, and counter.

使用4个变量:a,b,c和counter。

Initialize a, b, c by reading the 3 values.

通过读取3个值初始化a,b,c。

if (a+c)/2 == b, increment counter, and print a,b,c.

if(a + c)/ 2 == b,递增计数器,并打印a,b,c。

shift variables: a = b, b = c.

换档变量:a = b,b = c。

while cin >> c do:

而cin >> c做:

if (a+c)/2 == b, increment counter and print a,b,c.

if(a + c)/ 2 == b,增加计数器并打印a,b,c。

shift variables: a = b, b = c;

换档变量:a = b,b = c;

end-while.
Output value of counter.

计数器的输出值。

Looks very efficient to me.

对我来说看起来很有效率。

#1