二分答案 - 題目詳情 - HydroOJ

問題描述

給定一個由n個數構成的序列a，你可以進行k次操作，每次操作可以選擇一個數字，將其+1，問k次操作以后，希望序列里面的最小值最大。問這個值是多少。

輸入格式

第一行輸入兩個正整數n,k。(1≤n≤105,1≤k≤1013)
第二行輸入n個正整數，表示序列a。(1≤ai?≤106)

輸出格式

輸出最大的最小值

樣例輸入

5 10
1 4 2 6 8
Copy

樣例輸出

5
Copy

思路:

枚舉最小值的最大值，然后判斷是否可以成功，也就是使用操作次數是否在k范圍內。

代碼：
?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const ll N = 1e5 + 10;
ll n, k;
ll a[N];bool check(ll mid, ll k) 
{ll sum = 0;for (ll i = 1; i <= n; i++) {if (a[i] < mid) {sum += mid - a[i];}}return sum <= k;
}int main() {cin >> n >> k;ll min_val = LLONG_MAX;for (ll i = 1; i <= n; i++) {cin >> a[i];min_val = min(min_val, a[i]);}sort(a + 1, a + n + 1);ll l = min_val, r = 1e6 + k;while (l + 1 != r) {ll mid = (l + r) / 2;if (check(mid, k)) {l = mid;} else {r = mid;}}cout << l;return 0;
}