嵊州D2T1
“我只是来打个电话”
精神病院有一个这样的测试。
给出一个正整数集合,集合中的数各不相同,然后要求病人回答: 其中有多少个数,恰好等于集合中另外两个(不同的)数之和?
回答正确的人,即可以出院。
但是,条件是苛刻的—— 一秒。
直到变成废墟前,也没有人从中逃出。
但是如今不同了。
对吧?
Input
共两行,第一行包含一个整数 n,表示测试题中给出的正整数个数。
第二行有 n 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。
Output
一个整数,表示测验题答案。
Examples
telephone.in telephone.out
4 1 2 3 4 2
Notes
对于所有数据,满足 3 ≤ n ≤ 5000,给出的正整数不超过 10000。
Task1[50%]
n ≤ 100
Task2[100%]
无特殊限制
Solve!
这道题,我想出来的方法还是蛮多的。
O(n^3)的暴力枚举(10分!)
// 我的方法
sort(jh+,jh+n+,cmp);//从小到大sort排序
for(int k=;k<=n;k++)因为k要是两个数的和,所以它至少是第三个数吧?
{
for(int i=;i<=k;i++){
if(jh[i]==jh[k]) continue;
for(int j=i+;j<=k;j++){
if(k==j||jh[i]==jh[j]) continue;
if(jh[k]==jh[i]+jh[j]) out++;
}
} }
O(log2 n/*???*/)的二分法(后来有个不知名的原因做不出来)
我就直接在这里说最后的AC方法吧
要用两个数组:
int jh[MAXN], f[MAXN];
其中jh(集合)就是用来存你输入的数组的
f则是用来存有可能的和的(用1/0表示)
step1
两层循环,枚举所有的两数之和
step2
再从1开始扫描,遇到1(true)就out++;
没了!
#include<bits/stdc++.h>
using namespace std;
const int MAXN=;
int jh[MAXN], f[MAXN];
//bool cmp(int x,int y){return x<y?true:false;}
int main(){
//freopen("telephone.in","r",stdin);
//freopen("telephone.out","w",stdout);
int n; scanf("%d",&n);
int out=;
int jh[n+];
for(int i=;i<=n;i++) scanf("%d",&jh[i]);
bool f[MAXN];
memset(f,,sizeof(f));
for(int i=;i<=n;i++)
for(int j=;j<=i-;j++)
f[jh[i]+jh[j]]=;
for(int i=;i<=n;i++)
if(f[jh[i]]) out++;
printf("%d",out);
return ;
}
OK!