BGN75 构造三角形

思路

题目给了四个正整数 $a \le b \le c \le d$ ，要我们从三个区间 $[a, b]$ 、 $[b, c]$ 、 $[c, d]$ 各取一个数 $x, y, z$ ，使得它们能构成一个非退化三角形。

三角形的核心条件就是任意两边之和大于第三边。由于 $x \le y \le z$ （因为区间本身就是递增的），最紧的约束一定是 $x + y > z$ 。

那怎么让 $x + y > z$ 最容易满足呢？很自然的想法：让 $x$ 和 $y$ 尽量大， $z$ 尽量小。

$x$ 最大取 $b$
$y$ 最大取 $c$
$z$ 最小取 $c$

所以直接取 $(x, y, z) = (b, c, c)$ 。

验证一下三角形条件：

$x + y = b + c > c = z$ ，因为 $b \ge 1$ ，所以 $b + c > c$ 恒成立 ✓
$y + z = 2c \ge 2b > b = x$ ✓
$x + z = b + c > c \ge y$ ✓（同第一条）

三个条件全部满足，而且不需要任何特判。题目保证有解，我们的构造也确实总是合法的，完美！

构造题就是这样，找到一个巧妙的取值方式，比暴力枚举优雅多了。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        long long a,b,c,d;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        printf("%lld %lld %lld\n",b,c,c);
    }
    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();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long a = sc.nextLong(), b = sc.nextLong(), c = sc.nextLong(), d = sc.nextLong();
            sb.append(b).append(' ').append(c).append(' ').append(c).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    a, b, c, d = map(int, input().split())
    out.append(f"{b} {c} {c}")
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    const t = parseInt(lines[0]);
    const out = [];
    for (let i = 1; i <= t; i++) {
        const [a, b, c, d] = lines[i].split(' ').map(Number);
        out.push(`${b} ${c} ${c}`);
    }
    console.log(out.join('\n'));
});

复杂度

时间复杂度： $O(T)$ ，每组测试用例 $O(1)$ 。
空间复杂度： $O(1)$ 。

题解 | #构造三角形#

BGN75 构造三角形

思路

代码

复杂度