嵊州D2T1 “我只是来打个电话”

àì夳堔傛蜴生んèń 2021-11-22 17:40 189阅读 0赞

# 嵊州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+1,jh+n+1,cmp);//从小到大sort排序 
        for(int k=3;k<=n;k++)因为k要是两个数的和，所以它至少是第三个数吧？
        {
            for(int i=1;i<=k;i++){
                if(jh[i]==jh[k]) continue;
                for(int j=i+1;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=5001; 
    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=0;
        int jh[n+1];
        for(int i=1;i<=n;i++) scanf("%d",&jh[i]);
        bool f[MAXN];
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++) 
        for(int j=1;j<=i-1;j++)
            f[jh[i]+jh[j]]=1;
        for(int i=1;i<=n;i++)
        if(f[jh[i]]) out++;
        printf("%d",out);
        return 0;    
    }

OK！

转载于:https://www.cnblogs.com/send-off-a-friend/p/11177974.html