666

走不出的回忆
2025-05-23 16:32:38
发布于：浙江
8阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Stick {
    int length;
    int width;
};

// 自定义排序规则：先按长度降序，长度相同按宽度降序
bool compareSticks(const Stick& a, const Stick& b) {
    if (a.length != b.length) {
        return a.length > b.length; // 按长度降序
    }
    return a.width > b.width; // 长度相同，按宽度降序
}

int main() {
    int n;
    cin >> n;

    vector<Stick> sticks(n);
    for (int i = 0; i < n; ++i) {
        cin >> sticks[i].length >> sticks[i].width;
    }

    // Step 1: 按长度降序排序，长度相同则按宽度降序
    sort(sticks.begin(), sticks.end(), compareSticks);

    // Step 2: 初始化准备时间和已处理的棍子标记
    int preparation_time = 0;
    vector<bool> processed(n, false); // 标记棍子是否已被处理

    // Step 3: 遍历所有棍子，寻找最优加工顺序
    for (int i = 0; i < n; ++i) {
        if (!processed[i]) {
            preparation_time++; // 需要额外准备时间
            processed[i] = true; // 标记为已处理
            Stick last = sticks[i]; // 当前已处理的最后一根棍子

            // 寻找可以接在当前棍子后面处理的棍子
            for (int j = i + 1; j < n; ++j) {
                if (!processed[j] && sticks[j].length <= last.length && sticks[j].width <= last.width) {
                    processed[j] = true; // 标记为已处理
                    last = sticks[j];   // 更新当前已处理的最后一根棍子
                }
            }
        }
    }

    // Step 4: 输出结果
    cout << preparation_time << endl;

    return 0;
}
有帮助，赞一个
去预览
0/2000
这里空空如也
热门讨论
