(命题人)
基准时间限制: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;}