组栈、队列和stl习题

牛牛有一个数组长度大小为n，数组中有n个正整数。现在牛牛请你从其中选出三个元素（注意选择元素的下标不能相同，但是其值可以相同）组成一个三角形。

无法做到，请输出一行一个字符串"No solution"，反之请输出这三个元素的值。

如果有多种组成三角形的元素组合，你可以输出任意一种

核心思路

1. 三角形条件：三个数 能组成三角形当且仅当
2. 关键观察：将数组升序排序后，只需检查连续三个数是否满足条件。若存在解，则必存在一组连续三元组 满足

算法步骤

1. 若 ，直接输出 "No solution"
2. 将数组升序排序
3. 遍历下标 从 到 ：
   • 检查
   • 满足则输出这三个数并结束
4. 遍历完未找到解，输出 "No solution"

代码详解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    if (n < 3) {
        cout << "No solution" << endl;
        return 0;
    }

    sort(arr.begin(), arr.end());

    for (int i = 2; i < n; i++) {
        if (arr[i-2] + arr[i-1] > arr[i]) {
            cout << arr[i-2] << " " << arr[i-1] << " " << arr[i] << endl;
            return 0;
        }
    }

    cout << "No solution" << endl;
    return 0;
}

示例说明

• 输入：5 + [3, 4, 5, 1, 2]
  排序后：[1, 2, 3, 4, 5]
  检查：

  • : → ❌
  • : → ✔️ → 输出 2 3 4

• 输入：3 + [1, 2, 3]
  检查： → ❌ → 输出 No solution

复杂度

• 时间：（主要来自排序）
• 空间：（额外空间）