# Algorithm Notebook 3（3.1.2026~3.31.2026）

Canonical: https://www.mirstar.net/2026/03/01/alogorithm-notebook-3/
Author: onlymatt
Published: 2026-03-01T12:05:50.000Z
Updated: 2026-05-17T11:52:03.047Z
Categories: algorithm
Tags: algorithm notebook

## Luogu P1065 - 作业调度方案

题意：有n个步骤和机器，m个工件要进行作业调度，每个工件需要按照步骤1到n的顺序进行加工，每个步骤只能在特定的机器上进行，求按照指定的顺序完成所有工件的时间（题目要求从最早的地方开始）。

思路：使用计算机模拟填表的过程，使用finish[]记录每一个工件在操作的这一步之前完成的最后的截止时间，now_op记录现在在操作的工件的最新操作步骤，每次调度从finish[op]开始寻找**最先**的满足条件的时间点，更新finish[op]。

难点：难点在于可能会忽视题目特别提醒了的不可以先加工后面的步骤，应该先完成前面的步骤才能够完成后面的步骤，导致在寻找满足条件的时间点时没有考虑到这个限制条件。

```cpp
#include<iostream>
using namespace std;
const int MAXN = 20 + 5;
const int MAXT = 1e4;
struct workpiece{
    int machine[MAXN], time[MAXN];
}wp[MAXN];
int order[MAXN * MAXN], finish[MAXN], now_op[MAXN], machine[MAXN][MAXT];
int main(){
    int n, m, ans;
    cin >> m >> n;
    for (int i = 1; i <= n * m; i++) cin >> order[i];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> wp[i].machine[j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> wp[i].time[j];

    for (int i = 1; i <= n * m; i++){
        int op = order[i];
        int step = ++now_op[op];
        int machine_now = wp[op].machine[step];
        int time_needed = wp[op].time[step];

        int t = finish[op] + 1;
        while(true){
            bool flag = false;
            for (int j = t; j <= t + time_needed - 1; j++){
                if (machine[machine_now][j]) break;
                if (j == t + time_needed - 1) flag = true;
            }
            if (flag) break;
            else t++;
        }
        for (int j = t; j <= t + time_needed - 1; j++) machine[machine_now][j] = true;
        finish[op] = t + time_needed - 1;
        ans = max(ans, finish[op]);
    }
    cout << ans;
}
```

## Luogu P1786 帮贡排序

题意：有n个人，每个人有姓名、职务、帮贡和等级，按照帮贡从大到小排序，如果帮贡相同则按照输入顺序排序，输出排序后的结果。

思路：定义一个结构体来存储每个人的信息，使用sort函数进行排序，排序时按照帮贡从大到小排序，如果帮贡相同则按照输入顺序排序。

难点：一开始要忽略帮主和副帮主。

```cpp
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 110 + 5;
struct Person{
    int contribution, level, rank;
    string position, name;
};
string pos[] = {"","BangZhu","FuBangZhu","HuFa","ZhangLao","TangZhu","JingYing","BangZhong"};
int get_(string x){
    for (int i = 1; i <= 7; i++) if (pos[i] == x) return i;
    return 100;
}
int main(){
    int n;
    vector<Person> a, temp;
    cin >> n;
    for (int i = 1; i <= n; i++){
        int contribution, level, rank = i; string name, position;
        cin >> name >> position >> contribution >> level;
        Person p = {contribution, level, rank, position, name};
        if (position != "BangZhu" && position != "FuBangZhu")
            a.push_back(p);
        else temp.push_back(p);
    }
    sort(a.begin(), a.end(), [](const Person &a, const Person &b){
        if (a.contribution != b.contribution) return a.contribution > b.contribution;
        else if (a.rank != b.rank) return a.rank < b.rank;
        else return false; 
    });
    // for (int i = 0; i < n - 3; i++){
    //     int cnt = i + 1; // 第cnt名（按帮贡排序后）
    //     if (cnt <= 2) a[i].position = "HuFa";
    //     else if (cnt <= 6) a[i].position = "ZhangLao";
    //     else if (cnt <= 13) a[i].position = "TangZhu";
    //     else if (cnt <= 38) a[i].position = "JingYing";
    //     else a[i].position = "BangZhong";
    // }
    int cnt = 0;
    for (Person &p : a){
        cnt++;
        if (cnt <= 2) p.position = "HuFa";
        else if (cnt <= 6) p.position = "ZhangLao";
        else if (cnt <= 13) p.position = "TangZhu";
        else if (cnt <= 38) p.position = "JingYing";
        else p.position = "BangZhong";
    }
    for (Person p : temp) a.push_back(p);
    sort(a.begin(), a.end(), [](const Person &a, const Person &b){
        if (a.position != b.position) return get_(a.position) < get_(b.position);
        else if (a.level != b.level) return a.level > b.level;
        else if (a.rank != b.rank) return a.rank < b.rank;
        else return false;
    });
    for (Person p : a) cout << p.name << " " << p.position << " " << p.level << endl;
    return 0;
}
```

```cpp
for (Person &p : a)
```
是C++11引入的范围for循环，使用引用可以避免不必要的复制，提高效率。

```cpp
sort(a.begin(), a.end(), [](const Person &a, const Person &b){
    if (a.position != b.position) return get_(a.position) < get_(b.position);
    else if (a.level != b.level) return a.level > b.level;
    else if (a.rank != b.rank) return a.rank < b.rank;
    else return false;
});
```
这是使用lambda表达式作为排序的比较函数，按照职位、等级和输入顺序进行排序。

其中
```cpp
[](const Person &a, const Person &b)
```
是一个匿名函数，接受两个Person对象作为参数，返回一个bool值，表示a是否应该排在b前面。