题目大意是给定一个长度为奇数的数列,每次操作可以将数列中某个数加一,在k次操作之后问该序列能取到的最大中位数是多少。
原本想了个利用二分查找进行模拟的办法,复杂度是\( O(k \cdot n \cdot logn) \),结果TLE。后来想到可以二分答案。对于给定的k,k次操作以内使得数列中较大的那一半的数达到p,则答案至少为p。二分答案,复杂度为\( O(n \cdot logk) \)
#include <iostream> #include <algorithm> #include <vector> #include <string> #ifdef _MSC_VER #define scanf scanf_s #endif // _MSC_VER #ifndef ONLINE_JUDGE #define debug(x) std::cout<<x<<std::endl; #else #define debug(x) ; #endif; using namespace std; bool check(const vector<long long>& v, long long k, long long possible_median) { for (long long i = v.size() / 2; i < v.size() && v[i] < possible_median && k >= 0; ++i) { k -= possible_median - v[i]; } return k >= 0; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); long long n, k; cin >> n >> k; if (n == 1) { long long ans; cin >> ans; ans += k; cout << ans << endl; return 0; } vector<long long> arr(n); for (long long i = 0; i < n; ++i) { cin >> arr[i]; } sort(arr.begin(), arr.end()); long long low = 1, high = static_cast<long long>(1e18 + 5); long long mid; bool flag; while (low <= high) { mid = (low + high) >> 1; flag = check(arr, k, mid); if (flag) low = mid + 1; else high = mid - 1; } long long ans = flag ? mid : mid-1; cout << ans << endl; return 0; }
Comments | NOTHING