首页 > 其他 > 详细

HDU 2141(二分&三分 _B题)解题报告

时间:2018-01-24 00:14:51      阅读:234      评论:0      收藏:0      [点我收藏+]

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2141

-----------------------------------------------------------------------------------

题意:三个数组,找到每个数组中加和为M的值的组数。

思路:首先将后两个数组加和 O(N^2),排序 O(NlogN),然后利用二分求解。

代码:

技术分享图片
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
int c1=0;


int main(void){
    int L,M,N;
    while(~scanf("%d %d %d",&L,&M,&N)){
    int A[L]={0};
    int B[M]={0};
    int C[N]={0};
    for(int i=0;i<L;i++){
        scanf("%d",&A[i]);
    }
    for(int i=0;i<M;i++){
        scanf("%d",&B[i]);
    }
    for(int i=0;i<N;i++){
        scanf("%d",&C[i]);
    }
    int  SM =0;
    scanf("%d",&SM);
    int S[SM]={0};
    for(int i=0;i<SM;i++){
        scanf("%d",&S[i]);
    }
    int bcm = M*N;
    int BC[bcm];
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            BC[i*N+j]=B[i]+C[j];
        }
    }
    sort(BC,BC+bcm);
    int new_end = unique(BC,BC+bcm)-BC;
    c1++;
    printf("Case %d:\n",c1);
    for(int i=0;i<SM;i++){
    int flag =0;
    int tf =S[i];
    for(int j=0;j<L;j++){
        if(BC[(lower_bound(BC,BC+new_end,tf-A[j])-BC)]==tf-A[j]){
            flag =1;
            break;
        }
    }
    if(flag){
        printf("YES\n");
    }
    else{
        printf("NO\n");
    }    
    }
    
    
    }
    
    return 0;

}
View Code

 

HDU 2141(二分&三分 _B题)解题报告

原文:https://www.cnblogs.com/caomingpei/p/8338386.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!