codeforce-1201-C题解_C

概述题目：给你一个包含n个整数的数组A（n为奇数），对A做k次以下 *** 作：对数组排序使数组以非递减顺序排列。选取数组的中位数，然后加一最终使得数组的中位数最大。输入：第一行输入两个数字 n 和 k ——数组大小和进行的 *** 作次数输出：输出最大中位数栗子：输入　　3 2 　　　　　　　1 3 5 　　　输出　　5 （对于这个问题笔者刚开始想的按数组进行二分但是时间复杂度为O(kn)爆了所以更改思

题目：给你一个包含n个整数的数组A（n为奇数），对A做k次以下 *** 作：

对数组排序使数组以非递减顺序排列。选取数组的中位数，然后加一

最终使得数组的中位数最大。

输入：第一行输入两个数字 n 和 k ——数组大小和进行的 *** 作次数

输出：输出最大中位数

栗子：输入　　3 2

　　　　　　　1 3 5

　　　输出　　5

（对于这个问题笔者刚开始想的按数组进行二分但是时间复杂度为O(kn)爆了所以更改思路按值进行二分）

思路：最大中值，那么计算结束数组应该满足--从中间开始到中间后i位的值相等且等于最大中位数。

　　　首先定义一个的右值（右值应大于数组中的每一个元素，只要大于题目中给的1e9即可），求出其中位数。其次判断此中位数是否满足最大中位数的定义，若是，那么左值为此中位数（要求的是最大中位数）。若不是，那么右值为此中位数减一

check函数判断是否满足最大中位数的定义

bool check(ll mID) // 检查mID是否是真正的中值{    ll s = 0;    for (int i = n / 2; i < n; i++) {        if (mID > A[i])  // A[i] > mID A[i]是不进位的，因为就加不到A[i]那位            s = s + mID - A[i];    }    return (s <= k); // 当s > k时，要成为mID所需要的数比给的数多，则加不到mID那位 所以此mID}                   //  不是中值   此mID大了 如果小点那么可能就是中值了

然后缩小范围找最大中值

while (l < r) {        mID = (l + r + 1) / 2;        if (check(mID))  // 当mID是中值的时候可以选并且继续求大于mID的值是否满中值            l = mID;        else            r = mID - 1;  // mID不是中值的时候说明mID太大了，要往小的调    }

为什么mID = (l+r+1)/2？因为二分搜索一般用向下取整

详细请参考：https://www.cnblogs.com/flipped/p/4991658.html

完整代码：

#include <iostream>#include <algorithm>using namespace std;typedef long long ll;const int maxn = 200010;ll n,k,A[maxn];bool check(ll mID) // 检查mID是否是真正的中值{    ll s = 0;    for (int i = n / 2; i < n; i++) {        if (mID > A[i])  // A[i] > mID A[i]是不进位的，因为就加不到A[i]那位            s += mID - A[i];    }    return (s <= k); // 当s > k时，要成为mID所需要的数比给的数多，则加不到mID那位 所以此mID}                 //  不是中值   此mID大了 如果小点那么可能就是中值了int main(){    int i;    ll l = 0,r = 3e9;    ll mID;    scanf_s("%lld%lld",&n,&k);    for (i = 0; i < n; i++)        scanf_s("%lld",&A[i]);    sort(A,A + n);    while (l < r) {        mID = (l + r + 1) / 2;        if (check(mID))  // 当mID是中值的时候可以选并且继续求大于mID的值是否满中值            l = mID;        else            r = mID - 1;  // mID不是中值的时候说明mID太大了，要往小的调    }    printf("%lld",l);    return 0;}