免费设计商标,太原seo顾问,绍兴的网站建设公司,东营建设网题干#xff1a;
给出一个长度为N的整数数组A#xff0c;对于每一个数组元素#xff0c;如果他后面存在大于等于该元素的数#xff0c;则这两个数可以组成一对。每个元素和自己也可以组成一对。例如#xff1a;{5, 3, 6, 3, 4, 2}#xff0c;可以组成11对#xff0c;如…题干
给出一个长度为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
输出最大距离。
Sample Input
6
5
3
6
3
4
2
Sample Output
3
解题报告 这题第一反应是线段树但是想想思维题怎么可能上数据结构呢所以开始往思维方面想无非就是结构体存位置排序开一个数组存某个数最早(或晚)出现的位置等等方法呗、、、 线段树也不难想离散化一下之后从头到尾扫在离散化后的值那个权值那里存一下下标并标记说这个值已经出现过了即维护每个数字出现的最早时刻即最小下标然后扫到下一个数a[i]查询1~getpos(a[i])查询区间最小值维护差的最大值就可以了。getpos是找到a[i]对应的离散化以后的值。 这题我还想到了可否用setpair去维护在线更新set这样满足了每次查找的元素出现的先后关系但是对于值的大小emmm不好搞啊。反正51Nod - 1065这题是可以set做的。 这题看看代码就懂了题目中有两个要素元素的先后出现的关系关系是大于等于。排序的目的就是为了先满足后者因为后者最麻烦所以先让他满足为啥最麻烦呢因为看前后的话比较一下pos然后维护最小值就可以了但是对于值的话无法满足这个单调性也就是不好满足前缀可维护关系所以我们先排序排除了这个因素剩下的就是维护一个pos最小值了。
AC代码
#includebits/stdc.h
using namespace std;
int n,ans;
struct Node {int val,pos;
} node[50000 5];
bool cmp(const Node a,const Node b) {if(a.val! b.val) return a.val b.val;return a.pos b.pos;
}
int main()
{cinn;for(int i 1; in; i) {scanf(%d,node[i].val);node[i].pos i;}sort(node1,noden1,cmp);int curpos node[1].pos;for(int i 1; in; i) {curpos min(curpos,node[i].pos);ans max(ans,node[i].pos - curpos); }printf(%d\n,ans);return 0 ;
}
另如果要求了空间复杂度那么就不能排序解决了这时候考虑用优先队列去优化空间。 很巧妙但是可能只有面试的时候会遇到对空间有特别的要求的
AC代码2空间复杂度o(1)的版本
#includebits/stdc.h
using namespace std;
#define ll long long
struct Node {int val,pos;friend bool operator (Node x,Node y) {if(x.valy.val) return x.posy.pos;return x.valy.val;}
};
priority_queueNode pq;
int n;
int main() {cinn;Node tmp;for(int i 1; in; i) {scanf(%d,tmp.val);tmp.posi;pq.push(tmp);}int curn,ans0;while(!pq.empty()) {Node now pq.top();pq.pop();if(now.poscur) curnow.pos;ansmax(ans,now.pos-cur);}printf(%d\n,ans);return 0;
}
