贪心算法——加工木棍（C++）

上大学，一天是一天，两天也是一天。

——2024年6月27日

之前考试周断更了，今天重新开始！

题目描述

有n根木棍，已知每根木棍的长度和重量。这些木棍在木工机器上加工，机器准备加工木棍需要一些时间，称为设置时间。机器设置时间如下：

①第一根木棍设置时间为1min。

②在处理长度为l、重量为w的木棍之后，如果 l ≤ l' 且 w ≤ w' ，则长度为 l' ，重量为 w' 的木棍不需要设置时间，否则需要1分钟设置时间。现在要找到处理n根木棍的最短设置时间，例如有5根木棍，其长度和重量分别为（9，4），（2，5），（1，2），（5，3）和（4，1），那么最小设置时间应该是2min，加工顺序为（4，1），（5，3），（9，4），（1，2），（2，5）。

输入格式

输入两行，第一行有一个整数n（1 ≤ n ≤ 5000），表示测试用例重的木棍数量，第二行包含 2n 个整数 $l_1$ ， $w_1$ ， $l_2$ ， $w_2$ ，… $l_i$ ， $w_i$ …每个整数最大值为10000，其中 $l_i$ ， $w_i$ 分别为第 i 根木棍的长度和重量。

输出格式

每个测试用例在一行中输出，应包含以分钟为单位的最短设置时间。

输入样例

5
9 4 2 5 1 2 5 3 4 1

输出样例

题目解析

贪心法

本题与活动安排问题I类似，在求解最多兼容的活动个数时，我们是怎么考虑的呢？

要求最多能安排多少个活动，我们需要对每个活动按活动的结束时间递增排序，从第一个活动开始，以后的每个活动的开始时间都需要大于等于前一个活动的结束时间，这个题按照相同的思路，我们同样按长度递增排序（按重量排序同理），但这个题还需要满足木棍重量后者也需大于前者，所以还需在长度相同的情况下按重量进行递增排序，考虑用结构体重载函数实现。

以题目给的例子为例，按上述思路排序之后为：

（4，1），（1，2），（5，3），（9，4），（2，5）。

从第一个木棍开始遍历，如果同时满足长度和质量均大于前一个木棍，就对当前木棍进行标记，表示已经加工完毕，直到遍历到最后一个，再对总时间加一；然后再次重复这个过程，直到所有的木棍均被标记即退出循环。

题解代码

1. 构建木棍的结构体；

struct Action{int l;int w;// 构造重载函数Action(int l, int w):l(l), w(w) {}bool operator<(const Action &a) const{if(l == a.l){return w <= a.w;}return l <= a.l;}
};

2. 定义设置时间函数；

int minActionTime(vector<Action> &v){int len = v.size();// 定义最短时间int minTime = 0;int flag[v.size() + 1];memset(flag, 0, sizeof(flag));//用于标记木棍// 一定要先排序sort(v.begin(), v.end());for(int i = 0; i < len; i++){cout<<"当前木棍长度"<<v[i].l<<"，木棍质量"<<v[i].w<<endl;if(flag[i] == 0){//当前木棍还没有处理int pre = v[i].w;for(int j = i; j < len; j++){if(flag[j] == 0 && v[j].w >= pre){pre = v[j].w;flag[j] = 1;}}minTime++;}}return minTime;
}

3. 完整代码如下：

// 加工木棍
// 活动安排问题:第一个活动的结束时间小于等于第二个活动的开始时间#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>using namespace std;struct Action{int l;int w;// 构造重载函数Action(int l, int w):l(l), w(w) {}bool operator<(const Action &a) const{if(l == a.l){return w <= a.w;}return l <= a.l;}
};int minActionTime(vector<Action> &v){int len = v.size();// 定义最短时间int minTime = 0;int flag[v.size() + 1];memset(flag, 0, sizeof(flag));// 一定要先排序sort(v.begin(), v.end());for(int i = 0; i < len; i++){cout<<"当前木棍长度"<<v[i].l<<"，木棍质量"<<v[i].w<<endl;if(flag[i] == 0){//当前木棍还没有处理int pre = v[i].w;for(int j = i; j < len; j++){if(flag[j] == 0 && v[j].w >= pre){pre = v[j].w;flag[j] = 1;}}minTime++;}}return minTime;
}int main(){vector<Action> v;for(int i = 0; i < 5; i++){int l, w;cin>>l>>w;v.push_back(Action(l, w));}int res = minActionTime(v);cout<<"最少"<<res<<"分钟";return 0;
}