技术教程 编程教程 [LUOGU] P3611 [USACO17JAN]Cow Dance Show奶牛舞蹈 正文

[LUOGU] P3611 [USACO17JAN]Cow Dance Show奶牛舞蹈

2023-02-12,,,,

https://www.luogu.org/problemnew/show/P3611

二分答案+优先队列

二分O(logn) 判一次正确性O(nlogn) 总体O(nlognlogn)

为了让priority_queue变成小根堆，就把元素全部取相反数了。

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

inline int rd(){

  int ret=,f=;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-:;

  while(isdigit(c))ret=ret*+c-'',c=getchar();

  return ret*f;

}

const int MAXN=;

int n,t;

int d[MAXN];

priority_queue<int> Q;

bool check(int x){

  for(int i=;i<=x;i++) Q.push(d[i]);

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

    int top=Q.top();Q.pop();

    Q.push(top+d[i]);

  }

  int ret=;

  while(!Q.empty()){ret=max(ret,-Q.top());Q.pop();}

  return ret<=t;

}

int main(){

  n=rd();t=rd();

  for(int i=;i<=n;i++) d[i]=-rd();

  int l=,r=n;

  int ans;

  while(l<=r){

    int mid=(l+r)>>;

    if(check(mid))r=mid-,ans=mid;

    else l=mid+;

  }

  printf("%d\n",ans);

  return ;

}

[LUOGU] P3611 [USACO17JAN]Cow Dance Show奶牛舞蹈的相关教程结束。

《[LUOGU] P3611 [USACO17JAN]Cow Dance Show奶牛舞蹈.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!