我们遍历数组 ,将所有进步段的左端点和右端点存起来,然后将其按照右端点权值减左端点权值的大小为第一关键字、左端点为第二关键字进行排序,最后输出即可。
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
int a[N], n, T;
struct Node {
int l;
int r;
}t[N];
inline bool cmp (Node x, Node y) {
if (a[x.r] - a[x.l] == a[y.r] - a[y.l]) {
return x.l < y.l;
}
else {
return a[x.r] - a[x.l] > a[y.r] - a[y.l];
}
}
int main () {
scanf ("%d", &T);
int tot = 0;
while (T --) {
scanf ("%d", &n);
tot = 0;
for (int i = 1; i <= n; i ++) {
scanf ("%d", &a[i]);
}
int now = 1;
for (int i = 2; i <= n; i ++) {
if (a[i] >= a[i - 1]) {
continue;
}
else {
t[++ tot].l = now;
t[tot].r = i - 1;
now = i;
}
}
t[++ tot].l = now;
t[tot].r = n;//要记得在这里存,否则会漏掉最后一段。
sort (t + 1, t + 1 + tot, cmp);
for (int i = 1; i <= tot; i ++) {
if (a[t[1].r] - a[t[1].l] == a[t[i].r] - a[t[i].l]) {
printf ("%d %d ", t[i].l, t[i].r);
}//第一个段肯定最大,输出右端点权值减左端点权值和第一段相等的。
}
printf ("\n");
}
return 0;
}