51Nod－1305－Pairwise Sum and Divide

有这样一段程序，fun会对整数数组A进行求值，其中Floor表示向下取整：

fun(A)
sum = 0
for i = 1 to A.length
for j = i+1 to A.length
sum = sum + Floor((A[i]+A[j])/(A[i]*A[j]))
return sum

给出数组A，由你来计算fun(A)的结果。例如：A = {1, 4, 1}，fun(A) = [5/4] + [2/1] + [5/4] = 1 + 2 + 1 = 4。
Input
第1行：1个数N，表示数组A的长度(1 <= N <= 100000)。
第2 - N + 1行：每行1个数A[i]（1 <= A[i] <= 10^9)。
Output
输出fun(A)的计算结果。
Input示例
3
1 4 1
Output示例
4

一道找规律题，如果说，不考虑时间的话，那么这道题我知道三种解题思路，可是因为时间问题，这道题只有一种可以AC……

先看两种最直观最低效的算法，最后几组数据都超时了。

//超时...
//#include <stdio.h>
//
//int main(int argc, const char * argv[])
//{
   
// int N;
// int i, j;
// long long A[100001];
// long long sum = 0;
// scanf("%d", &N);
// 
// for (i = 0; i < N; i++)
// {
   
// scanf("%lld", A + i);
// }
// 
// for (i = 0; i < N; i++)
// {
   
// for (j = i + 1; j < N; j++)
// {
   
// sum += ((A[i] + A[j]) / (A[i] * A[j]));
// }
// }
// 
// printf("%lld\n", sum);
// return 0;
//}

这种写法就是将伪代码加工成代码而已，没有丝毫优化。
再看优化的一种。

//超时......
//#include <stdio.h>
//
//int main(int argc, const char * argv[])
//{
   
// int N;
// int i, j;
// long long A[100001];
// long long sum = 0;
// scanf("%d", &N);
// 
// for (i = 0; i < N; i++)
// {
   
// scanf("%lld", A + i);
// }
// 
// for (i = 0; i < N - 1; i++)
// {
   
// for (j = i + 1; j < N; j++)
// {
   
// if (A[i] > A[j])
// {
   
// A[i] ^= A[j];
// A[j] ^= A[i];
// A[i] ^= A[j];
// }
// }
// }
// 
// for (i = 0; i < N; i++)
// {
   
// if (A[i] == 1)
// {
   
// for (j = i + 1; j < N; j++)
// {
   
// if (A[j] == 1)
// {
   
// sum += 2;
// }
// else
// {
   
// sum += 1;
// }
// }
// }
// else if (A[i] == 2)
// {
   
// for (j = i + 1; j < N && A[j] == 2; j++)
// {
   
// sum += 1;
// }
// }
// else
// {
   
// break;
// }
// }
// 
// printf("%lld\n", sum);
// return 0;
//}

代码长度变长了，很明显它核心代码比第一种少了很多的运算次数，毕竟加法要比除法快很多，也省去了很多无用的加减乘除，原本是考虑每种组合，现在是只考了结果为1和2的组合，但是对这道题而言，这一丢丢的优化并不是太明显，并且多了上面的排序部分，显得很是得不偿失，如果用快排，也许会过，但是在用C写得情况下，快排需要自己去实现，就显得有些得不偿失了，代码长度会增加很多，如果用C++可以试试看。

接着，我们就来看第三种方法。

//AC...
#include <stdio.h>

int main(int argc, const char * argv[])
{
    int N;
    int i, j = 0;
    long long A[100001];
    long long sum = 0;
    scanf("%d", &N);

    for (i = 0; i < N; i++)
    {
        scanf("%lld", A + i);
        if (A[i] == 2)  //2单独处理
        {
            j++;
        }
        else if (A[i] == 1) //这里考虑到1和非1组合时结果为1、1和1组合时结果为2，
        {                   //而1和1的组合会被利用两次，所以与前者归并在一起考虑
            sum += N - 1;
        }
    }

    printf("%lld\n", sum + j * (j - 1) / 2);    //因为2和2组合会被利用两次
    return 0;
}

对于这种算法，需要分析一下，我们可以通过尝试发现，最后每个组合的结果无分三种，0、1、2，当然0的情况我们不需要进行运算考虑，那么我们就要考虑1和2，当1和非1组合、2和2组合时，结果为1，当1和1组合时，结果为2。所以我们只需要对A[i] == 1 || A[i] == 2的情况进行处理即可，上述代码注释写得很清晰，在此不过多解释了。。。。。。