题解 | #构造三角形#

题目链接

构造三角形

题目描述

给定四个正整数 $a, b, c, d$ ，满足 $a \le b \le c \le d$ 。需要构造三个整数 $x, y, z$ ，使得：

$a \le x \le b$
$b \le y \le c$
$c \le z \le d$
$x, y, z$ 可以构成一个非退化三角形。

题目保证至少存在一组解，输出任意一组即可。

解题思路

要使三条边 $x, y, z$ 构成三角形，它们必须满足三角形不等式：

$x + y > z$
$x + z > y$
$y + z > x$

我们来分析这三个条件。根据题目给定的取值范围： $x \in [a, b]$ , $y \in [b, c]$ , $z \in [c, d]$ 。

对于条件 $x + z > y$ ：我们知道 $x$ 的最小值为 $a$ ， $z$ 的最小值为 $c$ ， $y$ 的最大值为 $c$ 。因此， $x + z \ge a + c$ 。因为 $a$ 是正整数（ $a \ge 1$ ），所以 $a + c > c$ 。结合起来有 $x + z \ge a + c > c \ge y$ 。所以 $x + z > y$ 这个条件总是成立的。
对于条件 $y + z > x$ ：类似地， $y$ 的最小值为 $b$ ， $z$ 的最小值为 $c$ ， $x$ 的最大值为 $b$ 。因此， $y + z \ge b + c$ 。因为 $c$ 是正整数（ $c \ge b \ge a \ge 1$ ），所以 $b + c > b$ 。结合起来有 $y + z \ge b + c > b \ge x$ 。所以 $y + z > x$ 这个条件也总是成立的。
对于条件 $x + y > z$ ：这个条件不是必然成立的，需要我们通过构造来满足。为了更容易满足 $x+y > z$ ，一个自然的想法是让 $x$ 和 $y$ 尽可能大，让 $z$ 尽可能小。

让我们尝试一种最简单的构造方法：
- 在 $x$ 的范围 $[a, b]$ 中，取最大值 $x = b$ 。
- 在 $y$ 的范围 $[b, c]$ 中，取最大值 $y = c$ 。
- 在 $z$ 的范围 $[c, d]$ 中，取最小值 $z = c$ 。
现在我们来验证这组构造 $(x, y, z) = (b, c, c)$ 是否满足所有条件：
1. $a \le b \le b$ (成立，因为 $a \le b$ )。
2. $b \le c \le c$ (成立，因为 $b \le c$ )。
3. $c \le c \le d$ (成立，因为 $c \le d$ )。
4. 验证三角形不等式：
  - $x + y > z \implies b + c > c$ 。因为 $b$ 是正整数( $b \ge 1$ )，此式成立。
  - $x + z > y \implies b + c > c$ 。同样成立。
  - $y + z > x \implies c + c > b$ 。因为 $c \ge b$ ，所以 $2c \ge 2b$ 。由于 $b \ge 1$ , $2b = b+b > b$ 。因此 $2c > b$ 恒成立。
所有条件都满足。因此， $(b, c, c)$ 是一组必定满足条件的解。我们只需输出这三个数即可。

代码

c++
java
python

#include <iostream>

using namespace std;

void solve() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << b << " " << c << " " << c << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();
            long d = sc.nextLong();
            System.out.println(b + " " + c + " " + c);
        }
    }
}

def solve():
    a, b, c, d = map(int, input().split())
    print(b, c, c)

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：构造法。根据对三角形不等式和取值范围的分析，我们找到了一组简单的、必定符合条件的解 $(b, c, c)$ 。
时间复杂度：对于每组测试数据，我们只需要进行一次读入和一次输出，操作是常数时间的。如果共有 $T$ 组测试数据，则总时间复杂度为 $\mathcal{O}(T)$ 。
空间复杂度：我们只需要存储几个变量，因此空间复杂度为 $\mathcal{O}(1)$ 。