021：总和的圣礼（Sacrament of the sum）

Messj

描述

— The Brother of mine, the Head of Monastic Order wants to know tomorrow about the results long-term researches. He wants to see neither more nor less than the Summering Machine! Even moreover, he wants our Machine — only a machine — to demonstrate its comprehension of the Sacrament of the Sum as deeply as it is possible. He wants our Machine to find two numbers that give the sum equal to the Sacred Number 10 000.
— Tsh-sh-sh! This is madness that borders on blasphemy! How can the Machine calculate the Sacred Number? Twenty seven years we work on it, but we've could teach it to tell if the sum of two introduced numbers greater or lower than 10 000. Can an ordinary mortal find two numbers that there sum will be equal to 10 000?
— But we'll have to do it with the help of our Machine, even if it is not capable. Otherwise we'll have... let's say, big problems, if it is possible to call boiling oil like this. However, I have an idea. Do you remember, last week we've entered two numbers -7 and 13 into the Machine, and it answered that their sum is lower than 10 000. I don't know how to check this, but nothing's left for us than to believe to the fruit of our work. Let's enter now a greater number than -7 and start up the Machine again. We'll do like this again and again until we find a number that being added to 13 will give us 10 000. The only thing we are to do is to prepare an ascending list of numbers.
— I don't believe in this... Let's start with the sum that is obviously greater than the Sacred Number and we'll decrease one of the summand. So we have more chances to avoid boilin... big problems.

Haven't come to an agreement, the Brothers went away to their cells. By next day everyone of them has prepared a list of numbers that, to his opinion, could save them... Can both of the lists save them together?
Your program should decide, if it is possible to choose from two lists of integers such two numbers that their sum would be equal to 10 000.

输入

You are given both of these lists one by one. Format of each of these lists is as follows: in the first line of the list the quantity of numbers Ni of the i-th list is written. Further there is an i-th list of numbers each number in its line (Ni lines).The following conditions are satisfied: 1 <= Ni <= 50 000, each element of the lists lays in the range from -32768 to 32767. The first list is ascending and the second one is descending.

输出

You should write "YES" to the standard output if it is possible to choose from the two lists of integers such two numbers that their sum would be equal to 10 000. Otherwise you should write "NO".

样例输入

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

样例输出

YES

提示

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

Messj

题目描述

从前，有一对感情破裂的兄弟。为了拯救他们之间的感情，兄弟两人每个人都准备了一些对于他们来说可以拯救他们之间感情的数字，这些数字可以拯救他们的感情吗？(若在两个列表中的分别存在一个数，它们的和为10000，则我们认为这些数字可以拯救他们之间的感情)。你的程序应该决定，是否有可能从两个整数列表选择这样两个数字，来拯救他们的感情。

输入

每堆数（共2堆）的输入格式如下：每堆数的第一行，包含一个整数N ( 1 <= N <= 50,000 )，表示当前列表中的数字的个数；接下来N行，每一行包含一个整数A ( -32767<= A <=32767 )。输入数据保证：第一堆数按照升序排列，第二堆数按照降序排列。

输出

如果能找到符合要求的两个数，就输出"YES",否则输出"NO"

样例数据

样例输入       
4
-175
19
19
10424
3
8951
-424
-788

样例输出

YES

解析

由于两个数列都有序(连sort都不用)，直接对一个列表进行枚举，对另一个列表进行二分查找就行了。

#include<cstdio>

using namespace std;

int A[50000],B[50000];

int main()
{
        int n1,n2,mid,Max,Min;
        scanf("%d",&n1);
        for(int i=0;i<n1;i++)
                scanf("%d",&A[i]);
        scanf("%d",&n2);
        for(int i=0;i<n2;i++)
                scanf("%d",&B[i]);
        for(int i=0;i<n1;i++)
                for(Min=0,Max=n2-1,mid=(Max+Min)/2;Min<=Max;mid=(Max+Min)/2)
                {
                        if(A[i]+B[mid]==10000)
            {
                printf("YES");
                return 0;
            }
            else if(A[i]+B[mid]>10000)
                Min=mid+1;
            else
                Max=mid-1;
                }
        printf("NO");
        return 0;
}