博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
51 nod 最大距离
阅读量:5205 次
发布时间:2019-06-14

本文共 1130 字,大约阅读时间需要 3 分钟。

 

 

 (命题人)

基准时间限制:1 秒 空间限制:131072 KB 分值: 20

给出一个长度为N的整数数组A,对于每一个数组元素,如果他后面存在大于等于该元素的数,则这两个数可以组成一对。每个元素和自己也可以组成一对。例如:{5, 3, 6, 3, 4, 2},可以组成11对,如下(数字为下标):

(0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5)。其中(1, 4)是距离最大的一对,距离为3。

Input

第1行:1个数N,表示数组的长度(2 <= N <= 50000)。第2 - N + 1行:每行1个数,对应数组元素Ai(1 <= Ai <= 10^9)。

Output

输出最大距离。

Input示例

6536342

Output示例

3

如果我们把这些数从大到小排列,并且记录下这些数原本的位置,那么我们在找这两个数时,一定要找到位置在前的一个和位置在后的一个。保存那个小的位置就行。

实现一(优先队列)(AC):

#include
#include
using namespace std;struct A{ int value,key; friend bool operator < (A a,A b)//实现小根堆 { if(a.value==b.value) return a.key>b.key; return a.value>b.value; }}a[50000];priority_queue
q;//按小根堆来排列int main(){ int n; scanf("%d",&n); for(int i=0;i

实现二(AC):

#include
#include
using namespace std;struct A{ int value,key;}a[50000];bool cmp(A a,A b){ if(a.value==b.value) return a.key
mark)//找比当前最小位置,大的位置 result=max(result,a[i].key-mark); else mark=a[i].key;如果找到更小的则更新 } printf("%d\n",result); return 0;}

 

转载于:https://www.cnblogs.com/zut-syp/p/10543727.html

你可能感兴趣的文章
个人作业1——四则运算题目生成程序(基于控制台)
查看>>
创建Oracle synonym 详解
查看>>
【SQL】181. Employees Earning More Than Their Managers
查看>>
uva 1335 Beijing Guards
查看>>
php7 新特性整理
查看>>
Nodejs.Electron(Nodejs的图形界面开发)安装和试用
查看>>
RabbitMQ、Redis、Memcache、SQLAlchemy
查看>>
20190716NOIP模拟赛T2 通讯(tarjan缩点+贪心)
查看>>
退出shell 脚本
查看>>
Lua 字符串
查看>>
markdown简单语法总结
查看>>
一些基础的定义及事实集合
查看>>
linux查看端口占用
查看>>
hdu - 1226 超级密码 (bfs)
查看>>
Qt重写paintEvent方法遇到的问题
查看>>
Sql常见面试题 受用了
查看>>
关闭进程&关闭消息队列
查看>>
知识不是来炫耀的,而是来分享的-----现在的人们却…似乎开始变味了…
查看>>
vim在同一个窗口中同时编辑多个文件
查看>>
CSS背景颜色、背景图片、平铺、定位、固定
查看>>