Acwing136. 邻值查找（《算法竞赛进阶指南》）

2021-03-31 06:28

阅读：649

标签：lin 长度 fine printf char 提高 span color code

题目描述

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求：

min1≤j
以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。

输入格式

第一行输入整数n，代表序列长度。

第二行输入n个整数A1…An,代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共n-1行，每行输出两个整数，数值之间用空格隔开。

分别表示当i取2~n时，对应的min1≤j

数据范围

n≤105,|Ai|≤109

样例

输入样例：

3
1 5 3

输出样例：

4 1
2 1

本题用来巩固set的用法

 1 #include 2 #define int long long
 3 #define R register int
 4 #define PII pair 5 using namespace std;
 6 const int N=1e6+5,inf=1e12;
 7 inline int read()
 8 {
 9     char ch=getchar();int num=0;bool flag=false;
10     while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)flag=true;ch=getchar();}
11     while(ch>=‘0‘&&ch‘9‘){num=num*10+ch-‘0‘;ch=getchar();}
12     return flag?-num:num;
13 }
14 int n;
15 set s;
16 signed main()
17 {
18     n=read();
19     s.insert({inf,0});
20     s.insert({-inf,0});
21     for(R i=1;i)
22     {
23         int x=read();
24         PII u(x,i);
25         if(i>1)
26         {
27             auto t1=s.upper_bound(u);//t1->first是比x大的最小的值 
28             auto t2=t1;t2--;//t2->first是比x小的最大的值
29             int d1=x-t2->first,d2=t1->first-x;
30             if(d1"%lld %lld\n",d1,t2->second);
31             else printf("%lld %lld\n",d2,t1->second);
32         }
33         s.insert(u);
34     }
35     return 0;
36 }

此题为NOIP2012提高组开车旅行打基础

Acwing136. 邻值查找（《算法竞赛进阶指南》）

标签：lin 长度 fine printf char 提高 span color code

原文地址：https://www.cnblogs.com/ljy-endl/p/13569871.html

上一篇：springboot模板引擎之模板整合之thymeleaf（三）

下一篇：Http常见响应状态码

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Acwing136. 邻值查找（《算法竞赛进阶指南》）
文章链接：http://soscw.com/index.php/essay/70346.html

亲，登录后才可以留言！

Acwing136. 邻值查找（《算法竞赛进阶指南》）

题目描述

输入格式

输出格式

数据范围

样例

评论

热门文章

推荐文章

最新文章

置顶文章