首页 > 代码库 > uva:10487 - Closest Sums(二分查找)
uva:10487 - Closest Sums(二分查找)
题目:10487 - Closest Sums
题目大意:给出一组数据,再给出m个查询的数字。要求找到这组数据里的两个数据相加的和最靠近这个查询的数据,输出那两个数据的和。
解题思路:二分查找,这样找到的话,就输出查询的数值,但是要注意找不到的情况:这里最靠近的值不一定是在找不到的时刻的前一次数据,所以要维护最靠近的要查询数的数值。
代码:
#include <stdio.h> #include <algorithm> #include <stdlib.h> using namespace std; const int N = 1005; int s[N]; int n, q; int min (const int a, const int b) { if (a == 0) return b; return abs(a - q) < abs (b - q)? a: b; } int search () { int l = 0; int r = n - 1; int sum = 0; while (l <= n - 1 && r >= 0 && l < r) { if (s[l] + s[r] < q) { sum = min (sum, s[l] + s[r]); l++; } else if (s[l] + s[r] > q) { sum = min (sum , s[l] + s[r]); r--; } else return s[l] + s[r]; } return sum; } int main () { int m; int t = 0; while (scanf ("%d", &n), n) { for (int i = 0; i < n; i++) scanf ("%d", &s[i]); sort (s, s + n); scanf ("%d", &m); printf ("Case %d:\n", ++t); for (int i = 0; i < m; i++) { scanf ("%d", &q); printf ("Closest sum to %d is %d.\n", q, search ()); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。