Pairwise Sum and Divide 51nod

 
题目来源: HackerRank
基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题
Pairwise Sum and Divide 51nod 收藏
Pairwise Sum and Divide 51nod 关注
有这样一段程序,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

数学规律,只有1和2的数量对最后结果有影响/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
#define M 1000000007
/*
1 的效果,[(1+n)/n]
n=1 sum+=2 n>1 sum+=1
2 n =1,sum+=1,n=2,sum+=1,n>2,sum+=0;
3 [(3+n)/3*n] 1_1 2_0 3_0 4_0
4 [(4+n)/4*n] 1_1 2_0 3_0 4_0
只有1
----
设n1,n2,n-n1-n1分别为 1的个数,2的个数,其他的个数
最后结果等于
2*(n1*(n1-1)/2) //1和1之间
+ n2*(n2-1)/2
+ n1*(n-n1-n2)
*/
int main()
{
vector<LL> v;
LL n,t,cnt=,num=;
scanf("%lld",&n);
for(LL i=;i<n;i++)
{
scanf("%lld",&t);
if(t==)
cnt+=n-;
else if(t==)
num++;
}
printf("%lld\n",cnt+num*(num-)/);
return ;
}
上一篇:5天玩转C#并行和多线程编程 —— 第二天 并行集合和PLinq


下一篇:使用Jenkins配置Git+Maven的自动化构建