【2018 “百度之星”程序设计大赛 - 初赛（B）-1004】p1m2（迷之二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6383

题目就是让你求一个整数数组，在进行任意元素 + 1、 - 2 操作后，请问在所有可能达到的稳定数组中，拥有最大的『数组中的最小值』的那些数组，此值是多少呢？稳定数组是指数组中最大值 - 最小值 <= 1。

Sample Input

1 2 4

0 100000000

Sample Output

33333333

又想起那句“最大最小我tm一看就是二分”，然鹅知道是二分还是一脸懵逼QAQ

做法还是二分答案，怎么判断答案是否满足要求呢？让比答案小的数 + 1，比答案大的数 - 2，正解满足 + 1的数比 - 2的数多或者相等，如果不满足这个条件的话答案就不是数组中的最小值了。这里有一个坑点，就是在算 - 2的数有几个时一定要每加一个数 / 2，而不要算出num2之后再 / 2，因为这里存在奇数和偶数，仔细想想还是能明白的（在这里wa了2次 - -、）

#include <bits/stdc++.h>

using namespace std;

const int N = ;

typedef long long LL;

LL a[N];

LL n;

bool ok(LL x)

{

    LL num1 = , num2 = ;

    for(LL i = ; a[i] < x; i++)

    {

        num1 = num1 + (x - a[i]);//+1的个数

    }

    for(LL i = n - ; a[i] > x; i--)

    {

        num2 = num2 + (a[i] - x) / ;//-2的个数

    }

    if(num2 >= num1) return ;

    return ;

}

int main()

{

    LL t;

    cin>>t;

    //freopen("1.txt", "w", stdout);

    while(t--)

    {

        scanf("%lld", &n);

        for(LL i = ; i < n; i++)

        {

            scanf("%lld", &a[i]);

        }

        sort(a, a+n);

        LL l = a[], r = a[n-];

        while(l <= r)

        {

            LL mid = (l+r) >> ;

            if(ok(mid))

                l = mid + ;

            else

                r = mid - ;

        }

        printf("%lld\n", r);

    }

}

巴特西

【2018 “百度之星”程序设计大赛 - 初赛（B）-1004】p1m2（迷之二分）

Sample Input

Sample Output

最新文章

热门文章