列表

详情

NC24054. [USACO 2017 Jan S]Cow Dance Show

描述

After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia".

The only aspect of the show that remains to be determined is the size of the stage. A stage of size K can support K cows dancing simultaneously. The N cows in the herd () are conveniently numbered  in the order in which they must appear in the dance. Each cow i plans to dance for a specific duration of time d(i). Initially, cows  appear on stage and start dancing. When the first of these cows completes her part, she leaves the stage and cow K+1 immediately starts dancing, and so on, so there are always K cows dancing (until the end of the show, when we start to run out of cows). The show ends when the last cow completes her dancing part, at time T.

Clearly, the larger the value of K, the smaller the value of T. Since the show cannot last too long, you are given as input an upper bound  specifying the largest possible value of T. Subject to this constraint, please determine the smallest possible value of K.

输入描述

The first line of input contains N and , where  is an integer of value at most 1 million.
The next N lines give the durations  of the dancing parts for cows . Each d(i) value is an integer in the range .
It is guaranteed that if K=N, the show will finish in time.

输出描述

Print out the smallest possible value of K such that the dance performance will take no more than  units of time.

示例1

输入: 

5 8
4
7
8
6
4

输出: 

4

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 19ms, 内存消耗: 492K, 提交时间: 2019-04-21 15:05:21 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct cmp{
	bool operator() (int &a, int &b){
		return a > b;
		}
	};
priority_queue<int ,vector<int>,cmp>q;
int n,t;
int tim[maxn];
bool check(int x){
	for(int i = 1; i <= x; i++)
		q.push(tim[i]);
	int tot;
	for(int i = x + 1; i <= n; i++){
		tot = q.top();
		q.pop();
		tot += tim[i];
		if(tot > t) return false;
		q.push(tot);
		}
	while(!q.empty()) q.pop();
	return true;
	}
int main(){
	scanf("%d%d",&n,&t);
	for(int i = 1;i <= n; i++)
		scanf("%d",&tim[i]);
	int l = 1,r = n,ans;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid - 1,ans = mid;
		else l = mid + 1;
		}
	printf("%d\n",ans);
	return 0;
	}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 504K, 提交时间: 2020-09-17 17:01:32 

#include<bits/stdc++.h>
using namespace std;
int a[10010],n,m,ans;
priority_queue<int>q;
bool check(long long x){
	for(int i=1;i<=x;i++)
	q.push(-a[i]);
	int tot=x;
	while(q.size()){
		int y=-q.top();
		ans=y;
		q.pop();
		tot++;
		if(tot<=n)q.push(-y-a[tot]);
	}
	return ans<=m;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	cin>>a[i];
	long long l=0,r=n;
	while(l<r){
		long long mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<l<<"\n";
	return 0;
}

上一题

© 2024 nowcoder.com