首页 > 代码库 > 51nod 1272 最大距离
51nod 1272 最大距离
题目来源： Codility
基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
收藏
关注给出一个长度为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
贪心
屠龙宝刀点击就送
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node{ int hao,shu; }dian[60000]; bool cmp(node xx,node yy) { if (xx.shu!=yy.shu) return xx.shu<yy.shu; return xx.hao<yy.hao; } int main() { int n;scanf("%d",&n); for (int i=0;i<n;i++) { scanf("%d",&dian[i].shu); dian[i].hao=i; } sort(dian,dian+n,cmp); int ans=0,mi=dian[0].hao; for (int i=1;i<n;i++) { if (dian[i].hao>mi) ans=max(ans,dian[i].hao-mi); else mi=dian[i].hao; } printf("%d\n",ans); return 0; }
51nod 1272 最大距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。