题解 P3611 【[USACO17JAN]Cow Dance Show奶牛舞蹈】

zhaimingshuzms · 2017-05-16 20:00:59 · 题解

二分答案

对于每个二分的结果，进入判断函数判断其最大时间是否超过时限，用一个优先队列，每次把要下台的那只奶牛看成在台上又表演了下一只要上台的奶牛那么长时间，不断更新，在更新时如果已经超过时限就直接跳出，否则进入最后的统计，tmax和t_max进行比较，返回值；

时间复杂度O（n(logn）^2）；

其实我本来使用链表维护的，但是链表修改时（不是简单的修改，而是修改之后再排序的操作）严重超时，偶然想到了修改弹出都是logn的优先队列，就AC了这道题；

#########################################################

%:pragma GCC optimize(3)
#include<cstdio> 
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=10001;
int t[N],n,t_max;
priority_queue<int,vector<int>,greater<int> >q;
bool b(int k)
{
    int tmax=0,op,tt;
    for (int i=1; i<=k; i++) q.push(t[i]);
    for (int i=k+1; i<=n; i++)
    {
        op=q.top();  
        q.pop();
        op+=t[i];
        if (op>t_max) return 0;
        q.push(op);
    }
    for (int i=1; i<=k; i++) 
    {
        tt=q.top();
        if (tt>tmax) tmax=tt;
        q.pop();
    }
    return tmax<=t_max;
}
int main()
{
    scanf("%d%d",&n,&t_max);
    for (int i=1; i<=n; i++) scanf("%d",&t[i]);
    int ans=n;
    for (int l=1,r=n,mid=(l+r)>>1; l<=r; mid=(l+r)>>1)
    if (b(mid)) {ans=mid; r=mid-1;} else l=mid+1;
    printf("%d",ans);
    return 0;
}

################################################################# 本蒟蒻代码写的不好，勿喷