典型二分:杰瑞吃奶酪

发布时间 2023-09-24 19:56:38作者: chfychin

题目描述:

某一天,老鼠杰瑞抓住了一个机会,成功的到达了冰箱的附近,正当杰瑞打开冰箱门,想要享受美味的奶酪的时候,没想到冰箱里的奶酪太多了,奶酪洒了一地。汤姆猫听到了这个动静,正在火速赶往冰箱想要抓住杰瑞。杰瑞凭借与汤姆多年对抗的经历,仅凭借汤姆的脚步声便能推断汤姆还有多久抵达,现在,杰瑞并不怕汤姆,但汤姆抵达后必然影响杰瑞吃奶酪。于是杰瑞想要知道,在汤姆到达前,自己最多能吃到多少奶酪。

现在已知杰瑞与所有奶酪刚好排成一条直线,用坐标记录每个奶酪的位置,杰瑞一开始的坐标为0,杰瑞移动一个单位距离需要一个单位时间

由于杰瑞能一口吃下一整块奶酪,因此杰瑞吃奶酪的过程并不会花任何时间

输入格式:

第一行两个正整数t,n ,表示汤姆抵达需要的时间和奶酪的数量,
第二行n个整数,表示奶酪的坐标c。

输出格式: 一个整数,表示杰瑞最多能吃到的奶酪数量。

输入:

30 16
8 5 18 2 11 0 7 -14 -5 17 -11 15 -6 -16 10 1

输出:

13

点击查看代码
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 2e5 + 10;

int n, m, l, r, t, mid, ans, a[N];

bool check(int x)
{
	for(int i = 0; i <= n - x; i ++)
	{
		int j = i + x - 1;
		if(a[j] <= 0&&-a[i] <= t) return true;
		if(a[i] >= 0&&a[j] <= t) return true;
		if(a[i] <= 0&&a[j] >= 0)
			if(min(-a[i], a[j]) + (a[j] - a[i]) <= t) return true;
	}
	return false;
}

void solve()
{
	cin >> t >> n;
	for(int i = 0; i < n; i ++)
		cin >> a[i];
	sort(a, a + n);
	l = 1, r = n;
	while(l <= r)
	{
		mid = l + (r - l) / 2;
		if(check(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	cout << ans << '\n';
}

signed main()
{
	IOS;
	int _ = 1;
	// cin >> _;
	while(_ --) solve();
	return _ ^ _;
}