P14081 题解

songtaoran · 2025-09-27 18:49:18 · 题解

设区间为 [l,r]。
很容易看出来，l 就是满足最小能选出来 m 条边的 n，换句话说，最小的满足 \frac{n \times (n - 1)}{2} \ge m 的 n。
然后就是 r = 2 \times m - 2，因为此时可以 2 \times i - 1 与 2 \times i 连边，根据规则对面只能选出来 m - 1 条边。显然再大的不可能了。
记得判 l > r。
做完了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll T, m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> T;
    while(T--){
        cin >> m;
        ll l, r = 2 * m - 2, sq = sqrt(m * 2);
        for(ll i = max(1ll, sq - 10); i <= sq + 10; i++)
            if(i * (i - 1) / 2 >= m){
                l = i; break;
            } 
        if(l > r) cout << "Lose!\n";
        else cout << l << ' ' << r << '\n';
    }
    return 0;
}