首页 > 代码库 > hihocoder [Offer收割]编程练习赛14 小Hi和小Ho的礼物
hihocoder [Offer收割]编程练习赛14 小Hi和小Ho的礼物
题目1 : 小Hi和小Ho的礼物
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
某人有N袋金币，其中第i袋内金币的数量是Ai。现在他决定选出2袋金币送给小Hi，再选2袋金币送给小Ho，同时使得小Hi和小Ho得到的金币总数相等。他想知道一共有多少种不同的选择方法。
具体来说，有多少种下标四元组(i, j, p, q)满足i, j, p, q两两不同，并且i < j, p < q, Ai + Aj = Ap + Aq。
例如对于数组A=[1, 1, 2, 2, 2]，一共有12种选法：
i j p q1 3 2 41 3 2 51 4 2 31 4 2 51 5 2 31 5 2 42 3 1 42 3 1 52 4 1 32 4 1 52 5 1 32 5 1 4
输入
第一行包含一个整数N。
第二行包含N个整数，A1, A2, A3 ... AN。
对于70%的数据，1 <= N <= 100
对于100%的数据，1 <= N <= 1000, 1 <= Ai <= 1000000
输出
不同选择的数目。
- 样例输入
5 1 1 2 2 2
- 样例输出
12
//按两数和统计一下 注意去掉i == p or j == q的情况#include<map>#include<cstdio>#include<iostream>using namespace std;int n,a[(int)1e3+5],cnt[(int)1e6+5];map<int,int>sum;long long ans;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),cnt[a[i]]++; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) sum[a[i]+a[j]]++; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ ans+=sum[a[i]+a[j]]; if(a[i]!=a[j]) ans-=cnt[a[i]]+cnt[a[j]]-1; else ans-=2*(cnt[a[i]]-1)-1; } cout<<ans; return 0;}
hihocoder [Offer收割]编程练习赛14 小Hi和小Ho的礼物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。