18731 最接近的值

朱雀 2023-02-14 01:38 12阅读 0赞

时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定  
Description  
查找特定的值是一种常见的操作，当数据量较大时，往往需要使用高效的结构和查找算法。  
n个整数组成的序列，请输出所有元素左侧与它值最为接近的值，我们定义“最接近”为两数之差的绝对值最小。  
例如序列 5 1 4 2，1最接近值为5，4最接近值为5,2最接近值为1。  
特别的，第一个数的最接近值为它自身。  
如果一个数左侧有两个不同的值，绝对值差都是最小。例如3的左边出现了1和5，我们认为值较大的5为最接近值

输入格式  
第一行一个整数n。(1<=n<=100000)  
第二行n个整数，均为int范围。

输出格式  
一行，n个整数，为输入序列对应元素的最接近值。

输入样例  
4  
5 1 4 2

输出样例  
5 5 5 1

作者 30002692

解题思路：暴力：将第i个值插入，然后排序，再将该序列进行查找，看看其是否有前驱和后继，如果有的话，那么直接进行比较，然后取值就可以了，如果没有直接取，不用比较。  
进阶：使用multiset辅助排序和查找，其余的注意迭代器的过时问题就好。

#include<iostream>
    #include<set>
    using namespace std;
    int main()
    { 
    	ios::sync_with_stdio(0);
    	int n,i,x,v;
    	multiset<int> s;//多重集合
        multiset<int>::iterator it;
    	cin>>n;
    	cin>>x;
    	cout<<x<<' ';
    	s.insert(x);
    	for(i=2;i<=n;i++)
    	{ 
    		cin>>x;
    		s.insert(x);
    		it=s.lower_bound(x);//找出值x所在的位置 
            if(it==s.begin())//最前
            { 
            	it++;
            	cout<<*it<<' ';
            	continue;
    		}
    		it++;
    		if(it==s.end())//最后
    		{ 
    			it--;
    			it--;
    			cout<<*it<<' ';
    			continue;
    		 }
    		int last=*it;
    		it--;//复位 
    		int cur=*it;
    		it--;//往前调
    		int pre=*it;
    		if(cur-pre==last-cur)
    		{ 
    			cout<<last<<' ';
    		}
    		else if(cur-pre<last-cur)
    		{ 
    			cout<<pre<<' ';
    		}
    		else
    		{ 
    			cout<<last<<' ';
    		}	
    	}
    	return 0;
    }