[Codeforces]1389E – Weight Division
本文最后更新于 159 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/cf1399E/

E1

题意

给一棵带边权的树,每次操作可以使 $w:=\lfloor \dfrac{w}{2} \rfloor$,定义 $i \in leaves,W(i)$ 为叶子节点 $i$ 到根节点 $1$ 所经过的边权和,求 $\sum _{i \in leaves} W(i) \le S$ 的最少操作次数。

显然每条边经过的次数是固定的,对于连接 $(fa,u)$ 的边,经过次数为以 $u$ 为根的子树中叶子的个数。
定义每条边经过的次数为 $time(i)$,那么一条边减半的贡献是 $(w – \lfloor \dfrac{w}{2} \rfloor) \times time$,显然贪心每次取贡献最大即可。
优先队列维护一下。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <queue>

const int bufSize = 1e6;
using namespace std;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc())
        if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e5 + 100;
const int maxm = 2e5 + 100;
int T, n;
struct node
{
    int to, next, val;
} E[maxm];
int head[maxn], tot;
inline void add(const int& x, const int& y, const int& val) { E[++tot].next = head[x], E[tot].to = y, E[tot].val = val, head[x] = tot; }
long long S;
int sonleaf[maxn], fadis[maxn];
void dfs(int u, int fa)
{
    sonleaf[u] = 0;
    int flag = 0;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        fadis[v] = E[p].val, dfs(v, u);
        sonleaf[u] += sonleaf[v];
        flag = 1;
    }
    if (!flag) sonleaf[u] = 1;
}
struct choice
{
    int w, times;
    bool operator<(const choice& b) const
    {
        return 1ll * (w - w / 2) * times < 1ll * (b.w - b.w / 2) * b.times;
    }
};
priority_queue<choice> q;
int main()
{
    read(T);
    while (T--)
    {
        tot = 0;
        read(n);
        for (int i = 1; i <= n; ++i) head[i] = 0;
        read(S);
        for (int i = 1; i < n; ++i)
        {
            int a, b, c;
            read(a), read(b), read(c);
            add(a, b, c), add(b, a, c);
        }
        dfs(1, 0);
        while (!q.empty()) q.pop();
        long long now = 0;
        for (int i = 2; i <= n; ++i)
        {
            choice t;
            t.w = fadis[i], t.times = sonleaf[i];
            now += 1ll * fadis[i] * sonleaf[i];
            q.push(t);
        }
        int opt = 0;
        while (now > S)
        {
            choice t = q.top();
            q.pop();
            now -= 1ll * (t.w - t.w / 2) * t.times;
            t.w /= 2;
            if (t.w) q.push(t);
            ++opt;
        }
        printf("%d\n", opt);
    }
    return 0;
}

E2

题意

与 E1 大致相同,但每条边减半多了花费,花费 $\in [1,2]$,求最小花费。

解法

很自然的想法就是贪心顺延,贡献除以花费为优先值,然而——记得我们的背包问题吗?这样贪心显然是错误的。
那么考虑背包,显然暴力背包需要在每条边减半时都做一遍,复杂度是不可接受的。
可以对边权分组,每组中直接贪心,即 $f(i)$ 为花费为 $1$ 的边中,减半 $i$ 次的最大贡献,$g(j)$ 为花费为 $2$ 的边中,减半 $j$ 次的最大贡献。
理论上这是一个只有两组的分组背包,但既然只有两组,就不必跑背包了。
枚举在一组中的选择个数,计算出另一组最少选多少个能满足限制,即可计算出花费。
具体地,$f$ 与 $g$ 单调递增,枚举 $i$,要求 $f(i) + g(j) \ge sum – S$,且最小化 $i + j \times 2$,即最小化 $j$,那么用双指针的方法即可实现。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <queue>

const int bufSize = 1e6;
using namespace std;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e5 + 100;
const int maxm = 2e5 + 100;
int T, n;
struct node
{
    int to, next, val, cost;
} E[maxm];
int head[maxn], tot;
inline void add(const int& x, const int& y, const int& val, const int& cost) { E[++tot].next = head[x], E[tot].to = y, E[tot].val = val, E[tot].cost = cost, head[x] = tot; }
long long S;
int sonleaf[maxn], fadis[maxn], facost[maxn];
void dfs(int u, int fa)
{
    sonleaf[u] = 0;
    int flag = 0;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        facost[v] = E[p].cost, fadis[v] = E[p].val, dfs(v, u);
        sonleaf[u] += sonleaf[v];
        flag = 1;
    }
    if (!flag) sonleaf[u] = 1;
}
struct choice
{
    int w, times;
    bool operator<(const choice& b) const
    {
        return 1ll * (w - w / 2) * times < 1ll * (b.w - b.w / 2) * b.times;
    }
};
priority_queue<choice> q1, q2;
long long v1[maxn * 33], v2[maxn * 33], v1num, v2num;
int main()
{
    read(T);
    while (T--)
    {
        tot = 0;
        read(n);
        for (int i = 1; i <= n; ++i) head[i] = 0;
        read(S);
        for (int i = 1; i < n; ++i)
        {
            int a, b, c, d;
            read(a), read(b), read(c), read(d);
            add(a, b, c, d), add(b, a, c, d);
        }
        dfs(1, 0);
        while (!q1.empty()) q1.pop();
        while (!q2.empty()) q2.pop();
        v1num = v2num = 0;
        long long now = 0;
        for (int i = 2; i <= n; ++i)
        {
            choice t;
            t.w = fadis[i], t.times = sonleaf[i];
            now += 1ll * fadis[i] * sonleaf[i];
            if (facost[i] == 1) q1.push(t);
            else q2.push(t);
        }
        while (!q1.empty())
        {
            choice t = q1.top();
            q1.pop();
            ++v1num;
            v1[v1num] = 1ll * (t.w - t.w / 2) * t.times + v1[v1num - 1];
            t.w /= 2;
            if (t.w) q1.push(t);
        }
        while (!q2.empty())
        {
            choice t = q2.top();
            q2.pop();
            ++v2num;
            v2[v2num] = 1ll * (t.w - t.w / 2) * t.times + v2[v2num - 1];
            t.w /= 2;
            if (t.w) q2.push(t);
        }
        long long need = now - S;
        if (need <= 0)
        {
            puts("0");
            continue;
        }
        int p = 0;
        int ans = v1num + v2num * 2;
        for (int i = v1num; i >= 0; --i)
        {
            while (p <= v2num && v1[i] + v2[p] < need) ++p;
            if (p == v2num + 1) break;
            ans = std::min(ans, i + 2 * p);
        }
        printf("%d\n", ans);
    }
    return 0;
}
本文标题:[Codeforces]1389E – Weight Division
本文作者:Clouder
本文链接: https://www.codein.icu/cf1399e/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇