1 条题解

  • 0
    @ 2025-5-4 14:42:14

    分析:

    该代码使用了贪心算法和排序算法。通过对输入数据进行特定规则的排序,然后按照排序后的顺序进行遍历计算,以得到最优结果。 问题是要对一系列具有两个属性的数据进行处理,目标是找到一种排列顺序,使得完成所有数据处理的总时间最短。算法思想是先确定一个排序规则,让数据按照这个规则排序,然后按照排序后的顺序依次处理每个数据,从而得到最短的总处理时间。

    解题原理

    1.排序规则:核心在于定义了一个比较函数 comp,对于两个数据 x 和 y,通过比较 x.a + max(y.a, x.b) + y.b 和 y.a + max(x.a, y.b) + x.b 的大小来确定它们的顺序。这个比较函数的目的是让总处理时间更短的排列优先。具体来说,它考虑了两个数据在不同排列顺序下,完成它们所需的总时间,选择总时间更短的排列方式。

    2.贪心策略:按照排序后的顺序依次处理数据,在处理每个数据时,动态更新当前的总处理时间。每次处理一个新数据时,考虑前一个数据处理完的时间和当前数据的处理情况,更新总的处理时间。

    实现步骤

    1.输入读取:使用 while 循环不断读取数据的数量 n,当 n 为 0 时停止。对于每个 n,读取 n 组数据,每组数据包含两个整数 a 和 b,存储在结构体数组 po 中。

    2.数据排序:调用 sort 函数,使用自定义的比较函数 comp 对数组 po 进行排序。

    3.计算总时间:初始化两个变量 ans1 和 ans2 为 0。ans1 用于记录到当前数据为止,处理所有数据的 a 属性的总时间;ans2 用于记录到当前数据为止,处理所有数据的总时间。通过遍历排序后的数组 po,不断更新 ans1 和 ans2 的值。

    4.输出结果:输出最终的总处理时间 ans2。

    c++代码:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main() {
        int N;
        while (cin >> N && N != 0) {
            int a, b;
            int dp1 = 0, dp2 = 0;  // dp1 是前一个部件在 S1 结束的时间,dp2 是在 S2 结束的时间
            
            for (int i = 0; i < N; i++) {
                cin >> a >> b;
                // 当前部件在S1加工的最短时间
                dp1 = max(dp1, dp2) + a;
                // 当前部件在S2加工的最短时间
                dp2 = dp1 + b;
            }
            
            // 输出最早完成时间,即所有部件在S2完成的时间
            cout << dp2 << endl;
        }
        
        return 0;
    }
    
    • 1

    信息

    ID
    1751
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者