题解：P11204 「Cfz Round 9」Lone

Ren_Hx · 2024-10-19 17:40:20 · 题解

分析

在本题中，我们需要将一根长度为 m 的木棍分成 n 根小木棍，使得从中任选 3 根小木棍都可以组成一个三角形。而我们为了保证三根木棍可以组成三角形，则需要满足三角形不等式：

显而易见，对于任意三根木棍 g_1 , g_2 , g_3 ，满足：

但是值得注意的是，由于所有小木棍的长度都是正整数，所以，我总结了出以下几个要点：

• 最小的三根小木棍的长度需要大于半根棍子的长度。也就是说，若将最小的三根小木棍的长度记为 x ，那么 3x 必须小于等于 m 。（这点很重要）
• 将木棍分成 n 根，且每根木棍长度为正整数，因此 m 必须至少等于 n 。
• 为了满足三角形不等式，除了保证总长度 m 和小木棍数 n 之外，还需注意小木棍的长度分配。

思路

1. 检查 m 是否大于等于 n （每根小木棍长度至少为 1 ）。
2. 其次，计算 m 是否能被合理分配，以满足任意三根小木棍都能构成三角形，即 m 需要满足 m \geq 2n （这样可以使得能分成长度较小的木棍）。
3. 如果以上条件满足，则输出 Yes ，否则输出 No 。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n, m; 
        cin >> n >> m;
        if (m >= n && m >= 2 * n) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}