简证

重点来解释一下答案
先构造一种方案 答案是 ($cnt + 1 >> 1$)

假设有$n$棵子树 叶子（度为1的点）数$cnt$
那么
因为 $cnt >= n$

假设cnt < n
那么必定有n中至少一棵子树没有子节点
那么这个子树没有子节点 他就是叶子
不断可以调整至cnt >= n

那我可以直接连n棵子树
即 每棵子树中一个节点向另一棵子树节点 不重复的连边
这样 根与子树之间的边不是桥了
我们只需要把叶子连了即可
剩下的随意两两连
假如最后剩下一个（$cnt = 2k + 1(k为正整数)$） 连根节点
那么 我们就找到了一种方法 得出一种解

再证明这是最优解
考虑$cnt = 2k(k为正整数)$

因为我们每次都连了2个点 所以是$cnt / 2 = k$

每条边最多只能连2个点 而每个度为1的点都必须连接其他点
所以最优解 >= k 并且我们能构造一种方案= k
所以 k就是答案

对于$cnt = 2k + 1(k为正整数)$ 剩下那个点向根节点连即可

那么 即答案

$ans = (cnt + 1) >> 1$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[N];
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int faside)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if (i != (faside ^ 1)) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ dcc_cnt;
        int y;
        do {
            y = stk[top -- ];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    tarjan(1, -1);

    for (int i = 0; i < idx; i ++ )
        if (is_bridge[i])
            d[ id[ e[i] ] ] ++ ;

    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++ )
        if (d[i] == 1)
            cnt ++ ;

    printf("%d\n", (cnt + 1) >> 1);

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[N];
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int faside)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if (i != (faside ^ 1)) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ dcc_cnt;
        int y;
        do {
            y = stk[top -- ];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    tarjan(1, -1);

    for (int i = 1; i < idx; i ++ )
        if (is_bridge[i])
            d[ id[ e[i] ] ] ++ ;

    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++ )
        if (d[i] == 1)
            cnt ++ ;

    printf("%d\n", (cnt + 1) >> 1);

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];

struct Node
{
    int l, r;
    LL sum;
    LL d;
}tr[N << 2];

LL gcd(LL a, LL b)
{
    return b? gcd(b, a % b) : a;
}

void pushup(Node& u, Node& l, Node& r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        LL b = w[r] - w[r - 1];
        tr[u] = {l, r, b, b};
    }
    else
    {
        tr[u].l = l, tr[u].r = r;

        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}


void modify(int u, int x, LL v)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        LL b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    }
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}


Node query(int u, int l, int r)
{
    //if (l > r) return {0};
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);

    build(1, 1, n);

    char op[2];
    int l, r;
    LL v;
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);

        if (*op == 'Q')
        {
            auto left = query(1, 1, l);
            Node right({0, 0, 0, 0});
            if (l + 1 <= r) right = query(1, l + 1, r);
            printf("%lld\n", abs(gcd(left.sum, right.d)));
        }
        else
        {
            scanf("%lld", &v);
            modify(1, l, v);
            if (r + 1 <= n) modify(1, r + 1, -v);
        }
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 5e5 + 10;

int n, m, w[N];
struct Node
{
    int l, r, sum, lsum, rsum, tsum;
}tr[N << 2];

void pushup(Node& u, Node& l, Node& r)
{
    u.sum = l.sum + r.sum;
    u.lsum = max(l.lsum, l.sum + r.lsum);
    u.rsum = max(r.rsum, r.sum + l.rsum);
    u.tsum = max(max(l.tsum, r.tsum), l.rsum + r.lsum);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else
    {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        Node res;
        pushup(res, left, right);

        return res;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    int k, x, y;
    while (m -- )
    {
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1)
        {
            if (x > y) swap(x, y);
            printf("%d\n", query(1, x, y).tsum);
        }
        else modify(1, x, y);
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 2e5 + 10;

typedef long long LL;

struct Node
{
    int l, r, v;
}tr[N << 2];

int n, m, p, last;

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r)
{
    int trl = tr[u].l, trr = tr[u].r;
    if (l <= trl && trr <= r) return tr[u].v;
    int mid = (trl + trr) >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));

    return v;
}

void modify(int u, int x, int v)
{
    int trl = tr[u].l, trr = tr[u].r;
    if (trl == x && trr == x) tr[u].v = v;
    else
    {
        int mid = (trl + trr) >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int main()
{
    scanf("%d%d", &m, &p);
    build(1, 1, m);

    char op[2];
    int x;
    while (m -- )
    {
        scanf("%s%d", op, &x);

        if (*op == 'Q')
        {
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        }
        else
        {
            ++ n;
            modify(1, n, ((LL)last + x) % p);
        }
    }

    return 0;
}

思路

抽象一下题意 我们发现问题是：
把n拆分为两个正整数之积 
使这两个正整数之和减2最小

$于是我们有了最初想法 O（n^2）$

//暴力枚举
for (i = 1 ~ n)
      for (j = 1 ~ n)
           if (i * j == n)
              //操作

我们可以发现
只要找到n的第一个因数
那么第二个也随之确定
并且 我们发现
那个比较小的因数 一定<=sqrt(n)
(对于正整数n 大于sqrt_n的因数只有一个)
我们只需要枚举这个就可以

稳定$O(\sqrt{n})$

结论：最接近$O(\sqrt{n})$的两个因数之和最小

(接下来是数学证明 可以不看)
$设n = ab(a != b), n = c^2$
$(a + b)^2 - (2c)^2$
$= a^2 + 2ab + b^2 - 4c^2$
$= a^2 - 2ab + b^2$
$= (a - b)^2 >= 0$
$所以 (a + b)^ 2 >= (2c)^2$
$即 a + b >= 2c$
$这样 我们就证明了2个\sqrt{n}之和最小$
$因为 (a - b)^2 >= 0$
$所以 随着a与b差的增大 (a - b)^2单调递增（无论a, b怎么取）$
$即 a + b 越来越大 （c不变）$
证毕
$大概描述一下 当n确定时 横坐标为a, 纵坐标为a + b$
$样子大概是y = (x - \sqrt{n})^2 + 2\sqrt{n}那样$
但是要强调 并不是平方级增长 我只是描述这个趋势

最坏$O(\sqrt{n})$

AC代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

LL n, ans;

int main()
{
    scanf("%lld", &n);

    LL sqrt_n = sqrt(n);
    for (LL i = sqrt_n; i; -- i)
    {
        LL j = n / i;
        if (i * j == n)
        {
            ans = i + j - 2;
            break; 
        }
    }

    printf("%lld\n", ans);

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 30010;

int m;
int p[N], d[N], cnt[N];

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    scanf("%d", &m);
    for (int i = 1; i < N; i ++ )
    {
        p[i] = i;
        cnt[i] = 1;
    }
    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", , &a, &b);
        if (op[0] == 'M')
        {
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                d[pa] = cnt[pb];
                p[pa] = pb;
                cnt[pb] += cnt[pa];
            }
        }
        else
        {
            int pa = find(a), pb = find(b);
            if (pa == pb) printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
            else puts("-1");
        }
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_map>
using namespace std;

const int N = 2000010;

int n, m, T;
int p[N];
unordered_map<int, int> S;

struct Query
{
    int x, y, e;
}query[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int get(int x)
{
    if (!S.count(x)) S[x] = ++ n;
    return S[x];
}

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        n = 0;
        S.clear();
        scanf("%d", &m);
        for (int i = 1; i <= m; i ++ )
        {
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            query[i] = {get(x), get(y), e};
        }
        for (int i = 1; i <= n; i ++ ) p[i] = i;

        for (int i = 1; i <= m; i ++ )
            if (query[i].e)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                p[pa] = pb;
            }

        bool success = true;
        for (int i = 1; i <= m; i ++ )
            if (!query[i].e)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa == pb)
                {
                    success = false;
                    break;                        
                }
            }

        if (success) puts("YES");
        else puts("NO");
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 10010;

int n, m, k;
int p[N], v[N], w[N], f[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
    while (k -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            v[pb] += v[pa];
            w[pb] += w[pa];
            p[pa] = pb;
        }
    }

    for (int i = 1; i <= n; i ++ )
        if (p[i] == i)
            for (int j = m; j >= v[i]; j -- )
                f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d\n", f[m]);

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 40010;

int p[N];
int n, m, res;

int get(int a, int b)
{
    return a * n + b;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n * n; i ++ ) p[i] = i;

    for (int i = 1; i <= m; i ++ )
    {
        int x, y;
        char d;
        cin >> x >> y >> d;
        -- x, -- y;
        int a = get(x, y), b;
        if (d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);

        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            res = i;
            break;
        }
        p[pa] = pb;
    }

    if (res) printf("%d\n", res);
    else puts("draw");

    return 0;
}