NENUOJ 之 算法2贪心F

F001 木棒加工问题 (opens new window)

题目描述

现有n根木棒，已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。木工机需要的准备时间如下： （1） 第一根木棒需要1min的准备时间； （2） 在加工了一根长为l，重为w的木棒之后，接着加工一根长为l’（l≤l’），重为w’（w≤w’）的木棒是不需要任何准备时间的。否则需要一分钟的准备时间。 给定n根木棒，你要找到最少的准备时间。例如现在有长和重分别为（4,9），（5,2），（2,1），（3,5）和（1,4）的五根木棒，那么所需准备时间最少为2min，顺序为（1,4），（3,5），（4,9），（2,1），（5,2）。

输入

输入有多组测试例。输入数据的第一行是测试例的个数（T）。每个测试例两行：第一行是一个整数n（1≤n≤5000），表示有多少根木棒；第二行包括n*2个整数，表示l1,w1,l2,w2,l3,w3,…,ln,wn,全部不大于10000，其中li和wi表示第i根木棒的长度和重量。数据由一个或多个空格分隔。

输出

输出是以分钟为单位的最少准备时间，一行一个。

样例输入 复制

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

样例输出 复制

2
1
3

代码C++：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 7;

struct stick {
    int l, w;
} s[MAXN];

int vis[MAXN];

bool cmp(struct stick a,struct stick b) {
    if (a.l == b.l) return a.w < b.w; // 长度相同时按重量升序排序
    return a.l < b.l; // 按长度升序排序
}

void solve() {
    int n, ans = 0;
    cin >> n;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        cin >> s[i].l >> s[i].w;
    }
    sort(s + 1, s + n + 1, cmp);

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; // 已经使用过的木棒跳过
        ans++;
        int cur_l = s[i].l, cur_w = s[i].w;
        vis[i] = 1; // 标记当前木棒为已用
        for (int j = i + 1; j <= n; j++) {
            if (!vis[j] && s[j].l >= cur_l && s[j].w >= cur_w) {
                cur_l = s[j].l; // 更新当前长度
                cur_w = s[j].w; // 更新当前重量
                vis[j] = 1; // 标记为已用
            }
        }
    }
    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}