首页 > 其他分享 >P10466 邻值查找

P10466 邻值查找

时间:2024-09-13 17:27:22浏览次数:9  
标签:vector typedef P10466 return int long 邻值 查找 vx

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n);
	set<int> s;
	map<int,int> mp; 
	for(int i=0;i<n;++i) cin>>a[i];
	s.insert(a[0]);
	mp[a[0]] = 1;
	for(int i=1;i<n;++i)
	{
		auto it = s.lower_bound(a[i]);
		int val = 2e9, pos = 1e9;
		//注意读题要求的是选Ai更小的而不是下标
		if(it!=s.end()) {auto s = *it;val = s-a[i],pos = mp[s];}
		if(it!=s.begin()) 
		{
			it--;
			auto s = *it;
			if(a[i]-s<=val) val = a[i]-s, pos = mp[s];
		}
		cout<<val<<' '<<pos<<'\n';
		
		if(mp.find(a[i])==mp.end())
		{
			s.insert(a[i]);
			mp[a[i]] = i+1;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

标签:vector,typedef,P10466,return,int,long,邻值,查找,vx
From: https://www.cnblogs.com/ruoye123456/p/18412574

相关文章

  • 【每日一题】LeetCode 2576.求出最多标记下标(贪心、数组、双指针、二分查找、排序)
    【每日一题】LeetCode2576.求出最多标记下标(贪心、数组、双指针、二分查找、排序)题目描述给定一个整数数组nums,数组下标从0开始。你需要执行以下操作,直到无法再执行为止:选择两个互不相同且未标记的下标i和j。满足条件2*nums[i]<=nums[j],则标记下标i和j。......
  • 查找算法
    查找算法是用于在数据结构中查找特定元素的算法。根据数据的存储方式和组织形式,查找算法可以分为线性查找和二分查找等多种类型。以下是一些常见的查找算法及其特点:1.线性查找(LinearSearch)描述:从数据的第一个元素开始,依次与目标值比较,直到找到目标值或遍历完整个数据。时......
  • 算法与数据结构——二分查找插入点
    二分查找插入点二分查找不仅可用于搜索目标元素,还可以解决许多变种问题,比如搜索目标元素的插入位置。无重复元素情况Question给定一个长度为n的有序数组nums和一个元素target,数组不存在重复元素。现将target插入数组nums中,并保持其有序性。若数组中已存在元素target,则插入到......
  • 算法与数据结构——二分查找
    二分查找二分查找(binarysearch)是一种基于分治策略的高效搜索算法。它利用数据的有序性,每轮缩小一半搜索范围,直至找到目标元素或搜索区间为空为止。Qustion:给定一个长度为n的数组nums,元素按从小到大的顺序排列且不重复。请查找并返回元素target在该数组中的索引。若数组不包含......
  • python根据关键字查找文件所在路径位置
    importosimportfnmatchdeffind_files(directory,keyword):"""在给定目录及其子目录中查找包含关键词的文件"""forroot,dirs,filesinos.walk(directory):forbasenameinfiles:ifkeywordinbasename:......
  • LeetCode 704.二分查找 (java)
    给定一个 n 个元素有序的(升序)整型数组 nums和一个目标值 target ,写一个函数搜索 nums 中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例 2:......
  • OpenCV结构分析与形状描述符(19)查找二维点集的最小面积外接旋转矩形函数minAreaRect()
    操作系统:ubuntu22.04OpenCV版本:OpenCV4.9IDE:VisualStudioCode编程语言:C++11算法描述找到一个包围输入的二维点集的最小面积旋转矩形。该函数计算并返回指定点集的最小面积边界矩形(可能是旋转的)。开发者需要注意的是,当数据接近包含的Mat元素边界时,返回的Rotated......
  • 江西省毕业生如何查找档案存放地址
    江西省毕业生如何查找档案存放地址  毕业之后,学校不再保存个人的档案,要寄出去。政府机关、事业单位和国有企业有人事档案接收权,找到这些工作的同学,档案会寄到工作单位。而去私企、外企或者暂时不打算就业的同学,档案会寄到生源地,也就是户口所在地的人力资源局或人才市场。  ......
  • VSCode 常用快捷键总结:涵盖编辑器操作、文件管理、查找替换、代码格式化、调试、视图
    编辑器操作光标与选择Ctrl+D:匹配当前选中的词汇或行,再次选中可操作。Alt+Click:在多个位置插入光标。Ctrl+Alt+↑/↓:在上下行插入光标。Shift+Alt+I:在选中范围内所有行结束符插入光标。Shift+Alt+(dragmouse):鼠标拖动区域,同时在多个行结束符插入光标。Ct......
  • 【Python】排序算法及二叉树讲解(冒泡 选择 插入 二分查找 二叉树的广度优先和三种深
    排序算法​所谓排序,使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作​排序算法,就是如何使得记录按照要求排列的方法​排序算法在很多领域是非常重要​在大量数据的处理方面:一个优秀的算法可以节省大量的资源。​在各个领域中考虑到数据的......