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