简答题
偏难
#7205
找和最接近但不超过K的两个元素 在一个长度为n(1 < n < 1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过K(0 <=…
找和最接近但不超过K的两个元素
在一个长度为n(1 < n < 1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过K(0 <= K < 2000)。保证一定存在不超过K的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。
<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。
时间限制:1000
内存限制:65536
输入
第一行输入一个整数n 第二行输入一个整数K 第三行输入序列,用空格分开
输出
最接近但不超过K的和
样例输入
4 7 1 2 2 8
样例输出
4
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int a[10005];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int l = 0, r = n - 1;
int ans = a[0] + a[1];
while (l < r) {
int sum = a[l] + a[r];
if (sum <= k) {
if (k - sum < k - ans)
ans = sum;
}
if (sum == k) {
cout << k << endl;
return 0;
} else if (sum < k)
l++;
else
r--;
}
cout << ans << endl;
}</pre>
这道题暂未补解析。