#[USACO 2017 Jan S]Cow Dance Show#题解

题意

K头牛上台表演，最早表演完的牛下场按照表演顺序让接下来的牛表演，让你确定最小可同时上台表演的牛的数量K，使得他们表演的总时长不超过T。

做法：二分答案+优先队列

首先，确定二分答案，我们可以对表演的牛的数量二分，因为要求我们确定最小的可能数量，因此可写出以下代码：

    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    
    cout<<r<<endl;

接下来是关键的check函数呢，我们思考一下，根据题意，表演完了的要下场让牛按照表演的顺序依次上场，因此我们需要记录一下最早表演完的牛时间d[i]加上接下来要上场的牛的时间p.top()是否会超过我们的总时长，不合法直接返回，合法就利用优先队列更新一边即可，即：

bool check(int mid)
{
    priority_queue<int,vector<int>,greater<int>>p;
    
    //这里先预处理一边前mid头牛的最小时间
    for(int i=1;i<=mid;i++)p.push(d[i]);//d[i]表示每头牛表演时间
    
    for(int i=mid+1;i<=n;i++)
    {
        //当超过规定时间m返回
        if(d[i]+p.top()>m)return false;
        else
        {
            //合法就更新最小的表演时间
            int val=p.top();
            p.pop();
            p.push(val+d[i]);
        }
    }
    
    return true;
}