自动搬运

查看原文

来自洛谷，原作者为

	Strong_Jelly **

搬运于2025-08-24 21:50:44，当前版本为作者最后更新于2019-06-14 08:48:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先来介绍一下二分答案，二分答案是从一个区间内取一个中间值，判断是否符合题意（这里就先算要求最小值吧），符合则向更优的方向缩小范围（r = mid - 1），不符合则向能有可能的方向缩小范围（l = mid + 1）。 我们在这道题中需要二分k（及舞台上最多能跳多少牛），k越小结果就越优，所以当mid满足条件时，l就应该不变，r就应该 = mid - 1。

那么看代码吧（代码里注释有核心思路）（不会堆的看这里）

#include <bits/stdc++.h>
using namespace std;
int n, m, q[1000001];
inline bool f(int x)//这里x就是题目中的k 
{
	int y = 0;//y存的是上一头牛跳舞的结束时间 
	int ans = 0;//ans存时间和 
	priority_queue < int, vector < int >, greater < int > > pru;//堆的元素存的是牛的结束时间 
	for(register int i = 1; i <= x; ++i)//先把前k个跳舞的时间push进小根堆中 
	{
		pru.push(q[i]);//注意：只有这里是时间(不是结束时间) 
	}
	for(register int i = x + 1; i <= n; ++i)
	{
		ans += pru.top() - y;//这头牛的结束时间 - 上头牛的结束时间 = 又多用的时间 
		y = pru.top();//改为这头牛的结束时间 
		pru.pop();//弹出已经跳完舞的牛 
		pru.push(q[i] + y);//注意：要加上y才是这头牛的结束时间(上头牛的结束时间 + 这头牛跳舞需要的时间 = 这头牛的结束时间) 
		if(ans > m)//不能大于最大值 
		{
			return false;
		}
	}
	while(x--)//还差k个没有跳舞(加上跳舞时间) 
	{
		ans += pru.top() - y;//这些和上面相同 
		y = pru.top();
		pru.pop();
		//pru.push(q[i] + y);这里不能加，因为已经没有牛还在等待跳舞了(上面的循环他们都跳完了，现在所有牛不是在跳舞就是已经跳完了) 
		if(ans > m)
		{
			return false;
		}
	}
	return ans <= m;//其实这里直接return true就好了 
}
inline int half()//二分 
{
	int l = 0;
	int r = 100000;//开大点 
	int ans = 0;//最后的答案 
	while(l <= r)
	{
		int mid = (l + r) / 2;
		if(f(mid))
		{
			ans = mid;//mid可行 
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	return ans;
}
int main()
{
	scanf("%d %d", &n, &m);
	for(register int i = 1; i <= n; ++i)
	{
		scanf("%d", &q[i]);
	}
	//sort(q + 1, q + n + 1);这里不要排序，因为题目中说必须按牛在舞蹈中出现的顺序跳舞(1 ~ n) 
	printf("%d", half());
	return 0;
}