简答题 偏难
#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 &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int a[10005]; int main() {   int n, k;   cin &gt;&gt; n &gt;&gt; k;   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; a[i];   }   sort(a, a + n);   int l = 0, r = n - 1;   int ans = a[0] + a[1];   while (l &lt; r) {     int sum = a[l] + a[r];     if (sum &lt;= k) {       if (k - sum &lt; k - ans)         ans = sum;     }     if (sum == k) {       cout &lt;&lt; k &lt;&lt; endl;       return 0;     } else if (sum &lt; k)       l++;     else       r--;   }   cout &lt;&lt; ans &lt;&lt; endl; }</pre>
这道题暂未补解析。