3 条题解

  • 0
    @ 2025-7-16 11:50:26

    以下是为代码添加的完整注释,使用简单易懂的语言解释每一部分的功能,确保即使初学者也能理解:

    include<cstdio>    // 输入输出库(类似幼儿园的“说话工具”)
    
    include<algorithm> // 算法库(包含排序等工具)
    
    using namespace std; // 使用标准命名空间(避免重复写std::)
    
    // 定义任务结构体:每个任务有截止时间(t)和权重/收益(w)
    // 类似每个游戏任务有“最后完成时间”和“金币数量”
    struct node {
        int t; // 截止时间(比如第5天前必须完成)
        int w; // 权重/收益(完成任务的奖励金币数)
    a[1000100]; // 存放任务的数组(最多100万个任务)
    
    // 排序规则:按任务收益从大到小排序
    // 就像把最贵的玩具排在前面
    bool cmp(node x, node y) {
        return x.w > y.w; // 比较两个任务的金币数
    bool b[1000100]; // 标记数组:记录每天是否被占用(true=已用,false=空闲)
    
    int l[1000100];   // 并查集数组:记录每个日期的“空闲位置”
    
    // 查找空闲日期的函数(核心!)
    // 作用:快速找到某个日期之前最近的空闲日期
    int find(int x) {
        // 如果当前日期不是空闲(指向其他日期),就继续找它的“领导”
        if (l[x] != x) {
            l[x] = find(l[x]); // 路径压缩:直接让x指向最终的空闲日期
    return l[x]; // 返回找到的空闲日期
    
    int main() {
    
        int n, ans = 0; // n=任务数量, ans=总收益
        scanf("%d", &n); // 输入任务数量
    
        // 1. 读取每个任务的截止时间和收益
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &a[i].t, &a[i].w); // 格式:截止时间 收益
    // 2. 按收益从大到小排序(优先处理高收益任务)
    
        sort(a + 1, a + 1 + n, cmp);
    
        // 3. 初始化:每天都是空闲的,并指向自己
        for (int i = 1; i <= n; i++) {
            l[i] = i; // 第i天空闲位置初始是第i天
    // 4. 遍历所有任务(从收益最高的开始)
    
        for (int i = 1; i <= n; i++) {
            // 从截止时间往前找空闲日期
            for (int j = a[i].t; j >= 1; j = l[j]) { // 关键:通过l[j]跳到前一个空闲日
                if (!b[j]) { // 如果找到空闲日
                    b[j] = true;       // 标记这天已被占用
                    l[j] = l[j] - 1;   // 指向前一天(下次跳过已用日期)
                    ans += a[i].w;     // 累加当前任务的收益
                    break;             // 找到位置后跳出循环
    }
    
            // 更新截止时间的空闲位置(帮助后续任务快速查找)
            l[a[i].t] = find(a[i].t); 
    printf("%d", ans); // 输出总收益
    
        return 0;
    

    🌟 核心原理通俗解释(幼儿园版): 任务排序:

    把任务按金币数量从大到小排队,优先处理金币多的任务(类似先吃最甜的糖果)。 贪心策略:

    每个任务尽量在截止时间完成。如果截止时间被占,就往前找空闲日(比如截止周五,就试周四、周三...)。 并查集优化:

    l[] 数组像“跳跳杆”:遇到被占用的日期时,直接跳到前一个空闲日,避免重复检查[citation:7][citation:8]。

    find() 函数像“找座位向导”:快速找到最近的空座位(空闲日期)[citation:6]。 收益累加:

    只要任务找到空闲日完成,就把它的金币加入总收益 ans 中。

    ⚠️ 注意事项: 数组大小:代码预设数组大小为 1000100,若任务量超过此值需调整[citation:8]。

    时间范围:截止时间不能超过数组最大下标(否则越界)。

    适用场景:解决 带截止时间和收益的任务调度问题(如课程作业、工厂订单)[citation:8]。

    举个例子:假设有3个任务:

    任务A(截止第3天,收益50)

    任务B(截止第2天,收益30)

    任务C(截止第1天,收益20)

    程序会先执行A(占第3天,收益+50),再执行B(占第2天,收益+30),最后C(占第1天,收益+20),总收益=100。

    信息

    ID
    614
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    12
    已通过
    2
    上传者