专栏文章

题解：B4399 [蓝桥杯青少年组国赛 2025] 第四题

LLionBlaze
B4399题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio2fc4z
此快照首次捕获于
2025/12/02 12:15
3 个月前
此快照最后确认于
2025/12/02 12:15
3 个月前
查看原文
这题咋是 B4399……
带权区间覆盖。点 xx 的权值为 xx。最小化总权值。
先看经典的区间覆盖问题——无权区间覆盖，即最小化选点数量。按照右端点从小到大排序，遇到一个目前没有被覆盖的区间就选取其右端点。显然它是正确的，因为它让每个点都尽量靠右。
回到这题。尽量靠右会发生什么？选点数量尽量小的前提下，总权值尽量大。那我们从右向左贪心（同时按照左端点从大到小排序）不就是选点数量尽量小的前提下总权值尽量小吗？然后权值都是正数，所以总权值必然尽量小。
所以我们从右向左贪心即可。
显然要开 long long。
代码&提交记录CPP
#include <cstdio>
#include <algorithm>

using namespace std;

class seg
{
public:
    int l, r;
} segs[100005];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d", &segs[i].l, &segs[i].r);
    }
    sort(segs + 1, segs + n + 1, [](const auto &x, const auto &y) { return x.l > y.l; });
    int r = 1000000001;
    long long sum = 0;
    for(int i=1;i<=n;i++)
    {
        if(segs[i].r < r)
        {
            r = segs[i].l;
            sum += r;
        }
    }
    printf("%lld\n", sum);
    return 0;
}
record。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...