51nod - 1305 Pairwise Sum and Divide

思路：

Floor((A[i]+A[j])/(A[i]*A[j])) 可知A[i], A[j]只有在两个都为2或者至少有一个是1的时候这个值才不为0，即A[i], A[j]分别为1 1时贡献为2；2 2时贡献为1； 1 x， x 1时贡献为1；其他都为0；所以统计1和2的数量即可。

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1e5+5;int num[maxn], cnt1[maxn], cnt2[maxn], n;int main(void){    while(cin >> n)    {        memset(cnt1, 0, sizeof(cnt1));        memset(cnt2, 0, sizeof(cnt2));        int k1 = 0, k2 = 0;        for(int i = 0; i < n; i++)        {            scanf("%d", &num[i]);            if(num[i] == 1) k1++;            if(num[i] == 2) k2++;            cnt1[i] = k1;            cnt2[i] = k2;        }        int ans = 0;        for(int i = 0; i < n; i++)        {            if(num[i] == 1) ans += n-i-1+k1-cnt1[i];            else if(num[i] == 2) ans += k1-cnt1[i]+k2-cnt2[i];            else ans += k1-cnt1[i];        }        PRintf("%d/n", ans);    }    return 0;}
1305 Pairwise Sum and Divide题目来源： HackerRank基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注有这样一段程序，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示例
31 4 1Output示例
4