题目1352：和为S的两个数字
- 题目描述：
- 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
- 输入：
-
每个测试案例包括两行：第一行包含一个整数n和k，n表示数组中的元素个数，k表示两数之和。其中1 <= n <= 10^6，k为int第二行包含n个整数，每个数组均为int类型。
- 输出：
- 对应每个测试案例，输出两个数，小的先输出。如果找不到，则输出“-1 -1”
- 样例输入：
-
6 15 1 2 4 7 11 15
- 样例输出：
-
4 11
算法分析
既然是已经排序好的数组，那么从从两边分别开始查找，如果num[left] + num[right]==s则找到
如果num[left]+num[right]<s 则left++
如果num[left]+num[right]>s 则right--
源程序
输入用scanf，输出用printf，不然会超时
//============================================================================
// Name : judo1352.cpp
// Author : wdy
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
using namespace std;
int num[1000001];
void judo(int n,int s){
for(int i = 0;i<n;i++){
scanf("%d",num+i);
}
int Left = 0;
int Right= n-1;
while(Left < Right){
if(num[Left]+num[Right]==s){
break;
}
else if(num[Left]+num[Right] < s){
Left++;
}else{
Right--;
}
}
if(Left==Right){
printf("%d %d\n",-1,-1);
}else{
printf("%d %d\n",num[Left],num[Right]);
}
}
int main() {
int n;
int s;
while(scanf("%d %d",&n, &s) != EOF){
judo(n,s);
}
return 0;
}
/**************************************************************
Problem: 1352
User: KES
Language: C++
Result: Accepted
Time:1440 ms
Memory:5424 kb
****************************************************************/