首页 > 其他分享 >典型二分:杰瑞吃奶酪

典型二分:杰瑞吃奶酪

时间:2023-09-24 20:02:11浏览次数:25  
标签:二分 冰箱 汤姆 奶酪 杰瑞 int 坐标

题目描述:

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

现在已知杰瑞与所有奶酪刚好排成一条直线,用坐标记录每个奶酪的位置,杰瑞一开始的坐标为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 _ ^ _;
}

标签:二分,冰箱,汤姆,奶酪,杰瑞,int,坐标
From: https://www.cnblogs.com/chfychiin/p/17726520.html

相关文章

  • 算法基础之二分查找
    原题链接二分查找中的mid+1和mid-1的问题二分查找中的边界问题处理不好很容易导致死循环和计算错误的问题,以题目数的范围为例。题目大意​二分查找重复数第一次出现的位置和最后一次出现的位置。数学含义​第一次位置即找到一个长度最大的>=X区间的左边界​最......
  • 题单:二分
    【深基13.例1】查找题目描述输入\(n\)个不超过\(10^9\)的单调不减的(就是后面的数字不小于前面的数字)非负整数\(a_1,a_2,\dots,a_{n}\),然后进行\(m\)次询问。对于每次询问,给出一个整数\(q\),要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出\(-1\)。输入......
  • 随想录Day1|704. 二分查找、27. 移除元素
    随想录Day1|704.二分查找、27.移除元素 704.二分查找LeetCode题目文章讲解视频讲解给定n个元素升序的整形数组nums和一个目标值target,写一个函数搜索nums中的target,如果存在目标值则返回下标,否则返回-1。其中nums中的元素不重复,n在[1,10000]之间,nums的每个元素都在[-......
  • 算法学习 |Day 1 数组基础 704. 二分查找,27. 移除元素
    704.二分查找思路:二分查找的前置条件是数组有序且无重复元素,每次通过改变边界值来缩小查找范围。自己写的:可以看到对边界的判断存在问题,基本思路是左闭右闭,但是while循环的判断是按照左闭右开来写的。对于数组中仅包含一个元素且该元素是目标函数的情况会出错。重新调试后......
  • 代码源:合并数列(二分)
    有n个线性序列,第i个序列可以表示成ki×x+bi的形式(x=0,1,2,...)。请问将这些序列中的数按从小到大的顺序合并起来,前m个数分别是多少(重复出现的数合并后也会出现多次)?输入格式第一行一个整数n。接下来n行每行两个整数ki,bi。最后一行一个整数m。输出格式输......
  • LeetCode 周赛上分之旅 #46 经典二分答案与质因数分解
    ⭐️本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和BaguTreePro知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场LeetCode周赛的解题报告,一......
  • 二分图相关结论
    最小点覆盖:定义:选择最少的点,使得每条边都有一端被选。结论:二分图的最小点覆盖等于二分图最大匹配构造方案:从所有左侧未匹配的点出发,先走一条未匹配边,然后走一条匹配边,把所有走过的点标记,选择左边所有未标记的点和右边所有标记的点。最大独立集定义:选择最多的点,使得他们之间两......
  • 基础二分算法:整数二分、浮点二分
    1、整数二分以acwing789为例,题目要求如下:第一行输入整数n和q,表示数组长度和询问个数。第二行输入数组,包含n个整数。接下来q行,每一行一个整数k,表示一个问询元素。要求输出q行,每行包含两个整数,表示所求元素的起始位置和终止位置。如果数组中不存在该元素,则返回-1-1。#inc......
  • # 二分法
    l.sort()defindex(l,target_num):iflen(l)==0:print('没找到')returnmiddle_index=len(l)//2ifl[middle_index]<target_num:l_right=l[middle_index+1:]re......
  • 【学习笔记】(26) cdq 分治 与 整体二分
    cdq分治基本思想我们要解决一系列问题,这些问题一般包含修改和查询操作,可以把这些问题排成一个序列,用一个区间[L,R]表示。分。递归处理左边区间\([L,M]\)和右边区间\([M+1,R]\)的问题。治。合并两个子问题,同时考虑到\([L,M]\)内的修改对\([M+1,R]\)内的查询产生的影......