【洛谷题解】P3611【[USACO17JAN]Cow Dance Show S】

这是一道优先队列+二分的题

要选出最优的\(K\)，满足时间小于\(T_{max}\)

我们要在区间 \([ 1 , n ]\) 里二分答案

大致流程很简单：

• 二分一个 \(K\)

• 利用优先队列模拟跳舞流程，判断\(K\)是否合理

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,t,num[10005];
bool c(int x){
	/*利用优先队列模拟跳舞情况*/ 
	int at = 0;//当前k的耗时
	priority_queue < int,vector<int>,greater<int> > q;
	for(int i=1;i<=x;i++)q.push(num[i]);
	for(int i=x+1;i<=n;i++){
		int temp = q.top();q.pop();
		q.push(temp+num[i]);
	}
	while(!q.empty()){
		at = q.top();q.pop();
	}
	return at<=t;
}
int main(void){
	/*输入不解释*/
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>num[i];
	
	/*二分答案*/	
	int l=0,r=n,mid;
	while(l<=r){
		mid = (l+r)>>1;
		if(c(mid))r = mid-1;
		else l = mid+1;
	}
	cout<<l;
	return 0;
}

当然，如果大家觉得二分太麻烦的话。

\(K\)值直接从\(1\)枚举到\(n\)也是可以的

测试详情

直接枚举的代码：

#include<bits/stdc++.h>
using namespace std;
int n,t,num[10005];
bool c(int x){
	/*这里其实就是利用优先队列模拟跳舞情况*/ 
	int at = 0;
	priority_queue < int,vector<int>,greater<int> > q;
	for(int i=1;i<=x;i++)q.push(num[i]);
	for(int i=x+1;i<=n;i++){
		int temp = q.top();q.pop();
		q.push(temp+num[i]);
	}
	while(!q.empty()){
		at = q.top();q.pop();
	}
	return at<=t;
}
int main(void){
	/*输入不解释*/
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>num[i];
	int ans = 0;
    /*直接暴力枚举！*/
	for(int i=1;i<=n;i++){
		if(c(i)){
			ans = i;break;
		}
	}
	cout<<ans;
	return 0;
}

当然，这题数据较水

结束

各位看官，如果觉得还可以的话，点个赞吧~