牛客小白月赛44 A 深渊水妖

我们遍历数组 $aa$，将所有进步段的左端点和右端点存起来，然后将其按照右端点权值减左端点权值的大小为第一关键字、左端点为第二关键字进行排序，最后输出即可。

代码如下：

#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;
}