思路：双指针+优先队列/多重集合

要能够组成三角形，需要满足任意两边之和大于第三边的条件。而如果一个连续子序列中任意三个数都满足这个条件，则需要该区间中最小的两个值的和大于最大值。该需求可以考虑使用双指针进行求解。

从$1$到$i$枚举右指针，并维护左指针。左指针的变化要求指针间所有数中，最小的两个值的和要大于指针间所有数中最大的值，因此在将第$i$个数加入时，动态移动左指针以满足要求。

在维护时，可以同时维护两个优先队列，一个大根堆一个小根堆，并不断更新最大值和最小值，次小值即可。

代码

C++

#include <bits/stdc++.h>
using namespace std;

multiset<int> numSet;

// 检查当前multiset中是否有两个较小的数的和大于最大的数
bool isValid() {
    auto smallest = numSet.begin(), secondSmallest = next(smallest);
    auto largest = numSet.rbegin();
    return *smallest + *secondSmallest > *largest;
}

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> arr(n);

    for(int &x : arr) cin >> x;

    pair<int, int> maxRange = {0, 0}; // 记录最长区间的起始和结束位置
    numSet.insert(arr[0]);

    for(int start = 0, end = 1; end < n; ++end) {
        numSet.insert(arr[end]);

        // 如果当前区间不满足条件，则收缩区间
        while(!isValid()) numSet.erase(numSet.find(arr[start++]));

        // 更新最长区间
        if(end - start > maxRange.second - maxRange.first) {
            maxRange = {start, end};
        }
    }

    // 输出结果，区间的索引从1开始
    cout << maxRange.first + 1 << ' ' << maxRange.second + 1 << '\n';
}

int main() {
    solve();
    return 0;
}

题目内容

有$n$根木棍排成一列，第$i$根木棍的长度为$a_i$。

请你从中选出一个最长的子区间，使得区间内任意三根木棍都能构成三角形。只需要输出选出的区间端点即可。

输入描述

第一行一个整数$n(3≤n≤10^6)$，表示木棍的数量。

第二行$n$个整数，第$i$个整数$a_i(1≤a≤10^9)$表示第$i$根木棍的长度。

输出描述

输出一行两个整数，表示最长的满足条件的区间的两个端点，如果有多个满足条件的区间，输出左端点最小的区间。保证答案存在。

补充说明

示例1

输入

3
1 2 3

输出

1 2

说明

选取$2$根木棍也满足“任意三根木棍均能构成三角形"。

示例2

输入

9
2 3 3 3 1 1 3 3 3

输出

1 4