Level Generation

发表于 更新于 分类于 ，

    一个n个节点的图，至少有一半的边是桥。

    问边数最多能是多少？

Level Generation

Created by LXC on Wed May 3 12:50:29 2023

https://codeforces.com/problemset/problem/818/F

ranting: 2100

tag: binary search, math, ternary search

题意

一个n个节点的图，至少有一半的边是桥。

问边数最多能是多少？

题解

选x个点组成完全子图，共有x(x-1)/2条边。

剩下n-x个点形成链连接到这个完全子图，存在n-x条桥，所以完全子图中只能保留最多n-x条边。

函数
f(x) = min(x*(x-1)/2, n-x)+n-x, (1<=x<=n)
是凸函数。

我们用三分法求最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

ll n;

// 选x个点组成完全子图，共有x(x-1)/2条边，
// n-x个点形成链连接到这个完全子图，存在n-x条桥，所以完全子图中只能保留最多n-x条边

ll f(ll x) {
    return min(x * (x - 1) / 2, n - x) + n - x;
}

void sol() {
    cin >> n;
    // 至少选一个，至多选n个
    ll l = 1, r = n, lans = f(1), rans = f(n);
    while (l < r) {
        ll lmid = l + (r - l) / 3;  // l + 1/3区间大小
        ll rmid = r - (r - l) / 3;  // r - 1/3区间大小
        lans = f(lmid), rans = f(rmid);

        // 求凸函数的极大值
        if (lans <= rans)
            l = lmid + 1;
        else
            r = rmid - 1;
    }
    // 求凸函数的极大值
    cout << max(lans, rans) << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}