九度oj 题目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

今天状态真是差劲
一开始的代码如下

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int num[];

 int main(int argc, char const *argv[])

 {

     int n, k;

     while(scanf("%d %d",&n,&k) != EOF) {

         for(int i = ; i < n; i++) {

             scanf("%d",&num[i]);

         }

         int iptr = ;

         int mina = -, minb = -;

         while(iptr < n) {

             int p = k - num[iptr];

             int t = lower_bound(num, num + n, p) - num;

             if(num[t] == p && t > iptr) {

                     mina = num[iptr];

                     minb = p;

                     break;

             }

             iptr++;

         }

         printf("%d %d\n",mina, minb);

     }

     return ;

 }

思路很简单，用二分搜索找到另一个值在数组中的位置。结果反复提交都是错误

问题:lower_bound返回的是num[i]>=p的指针的最小值，

如果输入

5 2

1 1 1 2 5就会出错

改正

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int num[];

 int main(int argc, char const *argv[])

 {

     int n, k;

     while(scanf("%d %d",&n,&k) != EOF) {

         for(int i = ; i < n; i++) {

             scanf("%d",&num[i]);

         }

         int iptr = ;

         int mina = -, minb = -;

         while(iptr < n && num[iptr] *  <= k) {

             int p = k - num[iptr];

             int t = upper_bound(num, num + n, p) - num - ;

             if(num[t] == p && t > iptr) {

                     mina = num[iptr];

                     minb = p;

                     break;

             }

             iptr++;

         }

         printf("%d %d\n",mina, minb);

     }

     return ;

 }

其实此题还有一种更好的解法

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int num[];

 int main(int argc, char const *argv[])

 {

     int n, k;

     while(scanf("%d %d",&n,&k) != EOF) {

         for(int i = ; i < n; i++) {

             scanf("%d",&num[i]);

         }

         int low = , high = n-;

         int mina = -, minb = -;

         while(low < high) {

             if(num[low] + num[high] == k) {

                 mina = num[low];

                 minb = num[high];

                 break;

             }

             else if(num[low] + num[high] < k) {

                 low++;

             }

             else {

                 high--;

             }

         }

         printf("%d %d\n",mina, minb);

     }

     return ;

 }

注意找到的第一个便是乘积最小的！！！

巴特西

九度oj 题目1352：和为S的两个数字

最新文章

热门文章