hihoCoder#1095(二分搜索)

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

Little Hi and Little Ho are playing a drinking game called HIHO. The game comprises N rounds. Each round, Little Hi pours T milliliter of water into Little Ho's cup then Little Ho rolls a K-faces dice to get a random number d among 1 to K. If the remaining water in Little Ho's cup is less than or equal to d milliliter Little Hi gets one score and Little Ho drinks up the remaining water, otherwise Little Ho gets one score and Little Ho drinks exactly d milliliter of water from his cup. After N rounds who has the most scores wins.

Here comes the problem. If Little Ho can predict the number d of N rounds in the game what is the minimum value of T that makes Little Ho the winner? You may assume that no matter how much water is added, Little Ho's cup would never be full.

输入

The first line contains N(1 <= N <= 100000, N is odd) and K(1 <= K <= 100000).
The second line contains N numbers, Little Ho's predicted number d of N rounds.

输出

Output the minimum value of T that makes Little Ho the winner.

样例输入

5 6

3 6 6 2 1

样例输出

4

思路：求最值时考虑使用二分搜索。

#include <iostream>

using namespace std;

const int MAXN=;

const int INF=0x3f3f3f3f;

int n,k;

int d[MAXN];

bool test(int T)

{

    int cup=;

    int hi_score=;

    int ho_score=;

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

    {

        cup+=T;

        if(cup<=d[i])

        {

            hi_score++;

            cup=;

        }

        else

        {

            ho_score++;

            cup-=d[i];

        }

    }

    return ho_score>hi_score;

}

int main()

{

    cin>>n>>k;

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

    {

        cin>>d[i];

    }

    int l=,r=INF;

    while(r-l>)

    {

        int mid=(l+r)>>;

        if(test(mid))

        {

            r=mid;

        }

        else

        {

            l=mid;

        }

    }

    cout<<r<<endl;

    return ;

}

巴特西

hihoCoder#1095(二分搜索)

描述

输入

输出

最新文章

热门文章