NOIP2015普及组初赛 完善程序 第2题 《中位数》

Keywords: 中位数，二分法，noip2015

分析：

这是一道二分题目，先按照二分模板，大致写一下答案，然后模拟判断边界问题

下面是，填好的代码截图(DEV C++)

第三空填大于还是大于等于，不确定，需要模拟一下。假设填写 x[i] >mid，我们看一下结果是什么

好，看答案是正确的。那么过程是怎样的呢，我们再看一看

换成大于等于 x[i] >= mid，所得中位数的答案不正确。

当然，最重要的是背模板，看到l = mid +1 ，更新l的时候是mid + 1，那么，mid = l + r >> 1 ，没有+1

//按题面的程序版本，进行完善
//注意check函数的写法，二分答案

#include <bits/stdc++.h>

using namespace std;

int a[1010];
int n, m;

bool check(int x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (a[i] > x) cnt++;

    return cnt > n / 2;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    int l = 0, r = m, best = -1;
    while (l < r){
        int mid = (l + r) >> 1;

        if (check(mid)){
            l = mid + 1;
        }
        else{
            r = mid;
            best = mid;
        }   
    }

    cout << best << '\n';

    return 0;
}

// check函数的定义发生了变化

#include <bits/stdc++.h>

using namespace std;

int a[1010];
int n, m;

bool check(int x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (a[i] > x) cnt++;

    return cnt <= (n / 2);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    int l = 0, r = m, best = -1;
    while (l < r){
        int mid = (l + r) >> 1;

        if (check(mid)){
            r = mid;
            best = mid;
        }
        else
            l = mid + 1;
    }

    cout << best << '\n';

    return 0;
}

// 更换了二分模板，使用r = mid - 1

#include <bits/stdc++.h>

using namespace std;

int a[1010];
int n, m;

bool check(int x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (a[i] > x) cnt++;

    return cnt >= (n / 2);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    int l = 0, r = m, best = -1;
    while (l < r){
        int mid = (l + r + 1) >> 1;

        if (check(mid)){
            l = mid;
            best = mid;
        }
        else
            r = mid - 1;
    }

    cout << best << '\n';

    return 0;
}