【水】洛谷U249 匹配

时间：2014-10-21 22:48:32 阅读：267 评论：0 收藏：0 [点我收藏+]

题目描述 Description

输入整数s和两个整数集合A和B，从这A和B中各取一个数，如果它们的和等于s，称为“匹配”。编程统计匹配的总次数

输入输出格式 Input/output

输入格式：
第一行为三个整数s(0<s≤10000)、n和m(0<n,m≤50000)，其中n和m分别表示A和B集合中的元素个数；第二行表示集合A，一共n个整数ai(|ai|≤30000)，以空格隔开；第三行表示集合B，一共m个整数bi(|bi|≤30000)，以空格隔开
输出格式：
仅一个正整数，表示总次数

输入输出样例 Sample input/output

输入样例：

10000 4 3
-175 19 19 10424
8951 -424 -788

输出样例：

代码 codes

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstdlib>  
using namespace std;  
int n,m,s;  
int a[50004];  
int b[50004];  
int main()  
{  
    cin>>s>>n>>m;  
    for (int i=1;i<=n;i++) cin>>a[i];  
    for (int i=1;i<=m;i++) cin>>b[i];   
    sort(b+1,b+m+1);   
    int ans=0;  
    for (int i=1;i<=n;i++)  
    {  
        if (*lower_bound(b+1,b+m+1,(s-a[i]))==(s-a[i])) ans++;  
    }  
    cout<<ans;  
    return 0;   
}

注意

1.二分查找自己写的弱爆了………

#include<algorithm>
位置i=*lower_bound(b+1,b+m+1,(s-a[i]));

1.（from 桐学长mdwudier）
集合，什么是集合？集合是没有重复元素的大哥！
那样例？
样例比较逗…………

代码 codes

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstdlib>  
using namespace std;  
int n,m,s;  
int a[50004];  
int b[50004];  
int main()  
{  
    cin>>s>>n>>m;  
    for (int i=1;i<=n;i++) cin>>a[i];  
    for (int i=1;i<=m;i++) cin>>b[i];   
    sort(b+1,b+m+1);   
    int ans=0;  
    for (int i=1;i<=n;i++)  
    {  
        if (*lower_bound(b+1,b+m+1,(s-a[i]))==(s-a[i])) ans++;  
    }  
    cout<<ans;  
    return 0;   
}