礼物描述"/>
hiho1505 : 小Hi和小Ho的礼物描述
小Hi和小Ho的礼物 描述
某人有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 q 1 3 2 4 1 3 2 5 1 4 2 3 1 4 2 5 1 5 2 3 1 5 2 4 2 3 1 4 2 3 1 5 2 4 1 3 2 4 1 5 2 5 1 3 2 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
- 样例输出
对 i,j,p,q遍历的话时间复杂度会达到o(n4),所以考虑优化p,q。建立sum值的次数哈希与num出现次数的hash。
当固定了i,j时,可以求出当前的sum值,可以在刚刚建立的哈希表里找出当前sum值出现的次数,减去跟i,j重复值时的次数即为当前情况下的次数。
还是直接贴大神的思路 :
假设分配给小hi的金币为 a[i]
和a[j]
,现在的问题是求剩下的元素中有多少组 p, q
使得 a[i] + a[j] = a[p] + a[q]
。如果暴力枚举所有可能的 p, q
,需要 O(n^2)
时间,再加上枚举i, j
的时间,时间复杂度是 O(n^4)
,会超时。所以不能枚举 p, q
。
把输入保存在数组 a[]
中。
令 sumCnt[x]
表示两袋金币之和 a[i] + a[j] = x
组合数。
令 cnt[y]
表示元素 y
出现的次数。
假设分配给小hi的金币为 x = a[i] + a[j]
,那么x
一共有 sumCnt[x]
种可能的组合。
令 c1 = cnt[a[i]], c2 = cnt[a[j]]
,
假设 a[i] != a[j]
。
去掉a[i], a[j]
之前,a[i]
和a[j]
一共可以组成 c1 * c2
个 x
。去掉 a[i]
后,还有 c1 - 1
个与 a[i]
相同的元素,去掉 a[j]
后,还有 c2 - 1
个与 a[j]
相同的元素,它们还可以组成 (c1 - 1) * (c2 - 1)
个 x
。
所以,如果分配给小hi的金币为 a[i]
和a[j]
,那么存在 sumCnt - (c1 * c2 - (c1 - 1) * (c2 - 1))
对 p, q
使得 a[i] + a[j] = a[p] + a[q]
。
当 a[i] == a[j]
时,也是类似的处理。
p, q
的组数只需要 O(1)
,总的时间复杂度是 O(n^2)
。 代码: #include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int num[1002];
int main(){
freopen("E:\input.txt","r",stdin);
map<int,int> numcnt,sumcnt;
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
++numcnt[num[i]];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)
++sumcnt[num[i]+num[j]];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(num[i]!=num[j]){
ans+=sumcnt[num[i]+num[j]]-numcnt[num[i]]*numcnt[num[j]]+(numcnt[num[i]]-1)*(numcnt[num[j]]-1);
}else{
int cnt=numcnt[num[i]],left=cnt-2;
ans+=sumcnt[num[i]+num[j]]-cnt*(cnt-1)/2+left*(left-1)/2;
}
}
}
cout<<ans<<endl;
}
注意有点奇怪的地方是,ans需为long long,否则答案错误。明明为int时,暴力还能过70%。
更多推荐
hiho1505 : 小Hi和小Ho的礼物描述
发布评论