首页 > 其他分享 >【二分答案】P2390 地标访问

【二分答案】P2390 地标访问

时间:2024-06-09 22:46:51浏览次数:23  
标签:二分 P2390 int 一路 st 访问 地标 区间

\(\color{black}\text{P2390 地标访问 (传送门)}\)

学过区间 DP 的,看到这题的第一反应都是:访问的地标一定是一个区间,并且在不断扩大,区间 DP!可看到数据范围,又瞬间放弃了。与 P1220 关路灯 不同,这题由于没有电量的消耗等额外因素,有这样一个小性质:

  • 贝西的行走路线只可能是三种:一路向左,一路向右或者在中途折返一次。

一路向左和一路向右倒还好理解,可为什么最多只会折返一次呢?考虑以下情况:

如图,贝西从起点出发,折返了多次以访问所有地标。可问题是,以下做法不仅能满足要求,也更优:

换句话说,由于我们访问的地标总是一个区间,而从某个点开始走完整个区间分为三种情况:

  1. 起点在区间左边,一路向右;
  2. 起点在区间右边,一路向左;
  3. 起点在区间里,先前往比较近的端点(左端点或者右端点),再前往另一个端点走完整个区间。

那么,现在问题来了:我们到底能走多少个地标呢?这取决于我们拥有的时间 \(t\)。换句话说,这是在满足条件(所用时间 \(\bm{\le t}\))的情况下找最值。这不就是一个二分答案吗?而且单调性也是显然的:如果不能访问 \(x\) 个地标,那也访问不了 \(y(y>x)\) 个地标;如果能访问 \(x\) 个地标,那也访问的了 \(y(y<x)\) 个地标。

考虑二分答案。难点在于,如何设计 \(\text{check}\) 函数?假设当前二分答案猜测可以访问 \(X\) 个地标,则需要选择连续的 \(X\) 个地标(地标已经按坐标大小排序),即 \(x_1,x_2,\dots,x_X\) 或者 \(x_2,x_3,\dots,x_{X+1}\) 或者 \(x_3,x_4,\dots,x_{X+2}\ \dots\) 我们可以枚举这些区间的终点 \(i\in[X,n]\),则区间的起点为 \(st=i-X+1\)。考虑上面的三种情况:一路向右,一路向左,起点在区间里,只要有一个满足条件就返回 \(\text{True}\)。条件判断的表达式分别为:

x[st] >= 0 && x[i] <= t

x[i] <= 0 && abs(x[st]) <= t

x[st] <= 0 && x[i] >= 0 && min(abs(x[st]), x[i]) + x[i] - x[st] <= t

完全再现了上面的三种情况。

如此一来,代码也就非常好写了:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5e4 + 5;

int t, n, a[N];

bool check(int X) {
	for (int i = X; i <= n; i++) {
		int st = i - X + 1;
		if (a[st] >= 0 && a[i] <= t)
			return 1;
		else if (a[i] <= 0 && abs(a[st]) <= t)
			return 1;
		else if (a[st] <= 0 && a[i] >= 0 && min(abs(a[st]), a[i]) + a[i] - a[st] <= t)
			return 1;
	}
	return 0;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> t >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	int l = -1, r = 5e4 + 1;
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;
	return 0;
}

标签:二分,P2390,int,一路,st,访问,地标,区间
From: https://www.cnblogs.com/Weekoder/p/18240172

相关文章

  • AcWing算法基础课笔记——最小生成树与二分图
    目录朴素版prim算法——模板题AcWing858.Prim算法求最小生成树题目代码Kruskal算法——模板题AcWing859.Kruskal算法求最小生成树题目代码染色法判别二分图——模板题AcWing860.染色法判定二分图题目代码匈牙利算法——模板题AcWing861.二分图的......
  • 8621 二分查找
    Description 编写Search_Bin函数,实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法.输入格式第一行:元素个数n第二行:依次输入n个元素的值(有序)第三行:输入要查找的关键字key的值输出格式输出分两种情形:1.如果key值存在,则输出其在表中的位置x(表位置从0开......
  • C++ 6.8笔记:①判断质数②二分基础算法
    质数试除法判定质数boolprimes(intx){  if(x<2)returnfalse;  for(inti=2;i<=x/i;i++){    if(x%i==0)returnfalse;  }  returntrue;}埃筛1intp[N],k,n;boolf[N];voidprimes(intn){//埃筛,思想:质数的倍数是合数for(inti......
  • 二分查找相关题目(c++)
    1.元素编号输入 n个单调不减的(就是后面的数字不小于前面的数字)非负整数a1​,a2​,…,an​​,然后进行 m次询问。对于每次询问,给出一个整数 q,要求输出数列中第一个大于等于q的数字的编号。(若未找到则默认输出-1)输入共3行:第1行,2个整数n和m,表示数字个数和询问次数;......
  • PyTorch实现二分类任务
    importtorchimporttorch.nnasnnimporttorch.optimasoptim'''定义模拟数据集'''inputs=torch.randn(5,10)#定义5个样本,每个样本的特征数位10labels=torch.tensor([0,1,0,1,1])#每个样本的标签,二分类,所以为0或1'''定义模型''......
  • 代码随想录算法训练营第一天 | 704. 二分查找 27. 移除元素
    704.二分查找题目:给定一个n个元素有序的(升序)整型数组和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。提示:1.你可以假设nums中的所有元素是不重复的。2.n将在[1,10000]之间。3.nums的每个元素都将在[-9999,9999]之间。解题:思路:二......
  • 信息学奥赛初赛天天练-20-完善程序-vector数组参数引用传递、二分中值与二分边界应用
    PDF文档公众号回复关键字:2024060512023CSP-J完善程序1完善程序(单选题,每小题3分,共计30分)原有长度为n+1,公差为1等升数列,将数列输到程序的数组时移除了一个元素,导致长度为n的开序数组可能不再连续,除非被移除的是第一个或最后之个元素。需要在数组不连续时,找出......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素(数组)
    第一次打卡,记录还不够充分,会慢慢丰富起来一、二分查找题目链接:704.二分查找-力扣(LeetCode)讲解链接:Carl讲解视频讲解:代码随想录讲解 情况1:左闭右闭区间情况2:左闭右开区间 二、移除元素题目链接:27.移除元素-力扣(LeetCode)讲解链接:Carl讲解视频讲解:代码随想......
  • 代码随想录算法训练营第一天 | 704. 二分查找,27. 移除元素
    题目链接:704.二分查找思路:该题为有序数组查找,采用二分法。根据区间分为左闭右闭和左闭右开两种情况坑:左右区间的开闭补充:vector容器时间复杂度:O(logn)空间复杂度:O(1)题目链接:27.移除元素思路:题目说返回k个元素之后留下什么不重要,也不考虑数组剩下元素的......
  • Studying-代码随想录算法训练营day1| 数组理论基础,704二分查找,27.移除元素
    第一天......