B题能用二分吗?

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[5050], b[5050];
ll ans = -1;
ll n, m, u;
ll f = 0;
void check(ll x)
{
	f = 0;
	ll l = 1, r = x;
	ll alla = 0, allb = 0;
	while (r <= n)
	{
		for (int i = l; i <= r; i++)
		{
			alla += a[i];
			allb += b[i];
		}
		if (alla <= m && allb <= u)
		{
			ans = max(ans, x);
			f = 1;
			return;
		}
		else l++, r++;
		alla = 0, allb = 0;
	}
}
signed main()
{
	cin >> n >> m >> u;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	ll cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] <= m) cnt1++;
		if (b[i] <= u) cnt2++;
	}
	ll cnt = max(cnt1, cnt2);
	ll l = 0, r = cnt + 2;
	while (l < r)
	{
		ll mid = l + r >> 1;
		check(mid);
		if (f == 0) r = mid;
		else l = mid + 1;
		f = 0;
	}
	if (l == r)
		check(l);
	cout << l;
}

感觉二分思路很清楚,但卡在87.5%

全部评论
作者:牛客143949221号 链接:https://ac.nowcoder.com/discuss/1238900?type=101&order=0&pos=1&page=1&channel=-1&source_id=1 来源:牛客网 一天好像不是只能打一只怪兽,B题题意没有说一天只能打一只怪兽,而且有些怪兽打了不一定会增加声望,例如 4 7 10 2 3 4 5 -1 12 100 101 这组数据可以在第一天打两只怪兽,第二天打一只,所以最多是两天,但是你的输出为一天
点赞 回复 分享
发布于 2023-11-18 00:12 泛播
二分那部分应该写成 ```     while (l < r)     {         ll mid = l + r + 1>> 1;         check(mid);         if (f == 0) l = mid;         else r = mid - 1;         f = 0;     } ``` 吧,要找最大值不是?
点赞 回复 分享
发布于 2023-11-17 23:02 湖南
好像因为b_{i}可以是负数,在中途中可能就超出了,
点赞 回复 分享
发布于 2023-11-17 21:44 江苏
要边加变判断, check有问题
点赞 回复 分享
发布于 2023-11-17 21:41 重庆

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务