【三十七】【算法分析与设计】STL 练习，凌波微步，栈和排序，吐泡泡，[HNOI2003]操作系统，优先队列自定义类型

凌波微步

链接：登录—专业IT笔试面试备考平台_牛客网来源：牛客网

时间限制：C/C++ 1 秒，其他语言 2 秒

空间限制：C/C++ 32768K，其他语言 65536K

64bit IO Format: %lld

题目描述

小 Z 的体型实在是太胖了，每次和小 D 一起出门都跟不上小 D 的脚步，这让小 Z 很气馁，于是小 Z 跋山涉水，仿名山，遍古迹，终于找到了逍遥派。掌门看小 Z 求师虔诚，决定传小 Z 一套《凌波微步》。

这种腿法可以无视距离的行进，但缺点是只能走向高处，否则强行发功极易走火入魔。

一天，练习《林波微步》的小 Z 来到一处练武场，这里从左到右，共有 n 个木桩，这些木桩有高有低，在这里小 Z 勤奋的练习着凌波微步，你知道小 Z 在这处练武场最多能练习多少次么？

输入描述：

本题有 T 组数据。

对于每组数据第一行有一个正整数 n 表示有多少个木桩。

第二行有 n 个数 a_i，表示木桩与水平地面的相对高度。

1≤T≤10

1≤n≤100000

1≤a_i≤1000000000

输出描述：

输出结果，并换行。

示例 1

输入

复制 2 6 1 2 3 4 5 6 5 1 3 5 3 6

2

6

1 2 3 4 5 6

5

1 3 5 3 6

输出

复制 6 4

6

4

说明

第一组： 1->2->3->4->5->6 共 6 步

第二组： 1->3->5->6 共 4 步

题目要求我们对木桩进行去重和计数。

set容器的性质是去重+排序。

依次将数据insert进set中，然后输出size个数即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
        for (int i = 1; i <= T; i++) {
                int n; int ret = 0;
                cin >> n;
                set<int> a;
                for (int j = 1; j <= n; j++) {
                        int a_i; cin >> a_i;
                        a.insert(a_i);
                }
        ret=a.size();
                cout << ret <<endl;
        }
}

栈和排序

链接：登录—专业IT笔试面试备考平台_牛客网来源：牛客网

时间限制：C/C++ 1 秒，其他语言 2 秒

空间限制：C/C++ 131072K，其他语言 262144K

64bit IO Format: %lld

题目描述

给你一个 1->n 的排列和一个栈，入栈顺序给定

你要在不打乱入栈顺序的情况下，对数组进行从大到小排序

当无法完全排序时，请输出字典序最大的出栈序列

输入描述：

第一行一个数 n

第二行 n 个数，表示入栈的顺序，用空格隔开，结尾无空格

输出描述：

输出一行 n 个数表示答案，用空格隔开，结尾无空格

示例 1

输入

复制 5 2 1 5 3 4

5

2 1 5 3 4

输出

复制 5 4 3 1 2

5 4 3 1 2

说明

2 入栈；1 入栈；5 入栈；5 出栈；3 入栈；4 入栈；4 出栈；3 出栈；1 出栈；2 出栈

我们的目的是尽可能在可以输出的元素中，输出最大值元素。

可以输出的元素是指栈顶元素，和还没有入栈的元素。

每一次都是在这个集合中输出最大值。

如果目标值位于栈顶，直接输出。如果目标值位于还没入栈的集合中，需要不断入栈直到目标元素位于栈顶。

我们用 a 存储入栈序列。

定义 waiting 存储还没有处理的元素。

宏观的思想，依次处理元素，直到 waiting 集合中没有元素为止。

定义 ans 存储结果序列。

定义 stk 模拟入栈出栈操作。

依次将 waiting 中还没有处理的元素入栈进行处理。

处理内部逻辑，判断是否是目标元素，如果是目标元素，则栈顶元素要大于未处理集合中的所有元素。waiting 集合用 set 容器存储。只需要比较栈顶元素和未处理集合中最后一个元素的大小就可以知道是不是目标元素。

如果是目标元素，添加到 ans 中，然后出栈。

可以想象 stk 和 ans 整体是已经处理的集合。

处理完毕时，目标元素位于未处理集合中。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    stack<int> stk;
    vector<int> ans;
    set<int> waiting;

    for (int i = 1; i <= n; ++i) {
        waiting.insert(i);
    }

    for (int i = 0; i < n; ++i) {
        stk.push(a[i]);
        waiting.erase(a[i]);

        while (!stk.empty() && !waiting.empty() && *waiting.rbegin() < stk.top()) {
            ans.push_back(stk.top());
            stk.pop();
        }
    }

    while (!stk.empty()) {
        ans.push_back(stk.top());
        stk.pop();
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " ";
    }

    return 0;
}

吐泡泡

链接：登录—专业IT笔试面试备考平台_牛客网来源：牛客网

时间限制：C/C++ 1 秒，其他语言 2 秒

空间限制：C/C++ 32768K，其他语言 65536K

64bit IO Format: %lld

题目描述

小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。

两个相邻的小泡泡会融成一个大泡泡，两个相邻的大泡泡会爆掉。

（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。)

例如：ooOOoooO 经过一段时间以后会变成 oO。

输入描述：

数据有多组，处理到文件结束。

每组输入包含一行仅有'O'与'o'组成的字符串。

输出描述：

每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

示例 1

输入

复制 ooOOoooO

ooOOoooO

输出

复制 oO

oO

说明

自左到右进行合并

备注：

对于 100%的数据，

字符串的长度不超过 100。

定义 a 集合中，全是融合好的元素集合。

将 s 中未处理的元素，依次加入到 a 集合中。

加入一个未处理的元素之后，维护 a 集合定义，全都是融合好的元素。

维护定义内部逻辑，如果最后两个字符相同，进行处理。处理完之后还需要判断最后两个，直到最后两个元素不同为止。处理细节，确保有两个元素，判断 size 是否大于等于 2。

静态定义，a 集合都是处理好的元素，另一个集合是还没有处理的元素。

依次将还没有处理的元素，放到 a 集合中，然后维护 a 集合的定义。直到还没有处理的集合为空集，此时 a 集合就是全部元素处理好的集合。

#include<bits/stdc++.h>
using namespace std;

int main() {
        string s;
        while (cin >> s) {
                vector<char> a;
                int n = s.length();
                for (int i = 0; i < n; ++i) {
                        a.push_back(s[i]);
                        while (a.size()>=2 && a[a.size() - 1] == a[a.size() - 2]) {
                                char ch;
                                ch = a[a.size() - 1];
                                a.pop_back();
                                a.pop_back();
                                if (ch == 'o')a.push_back('O');
                        }
                }
                for (int i = 0; i < a.size(); ++i) {
                        cout << a[i];
                }
                cout << endl;
        }
}

[HNOI2003]操作系统

链接：登录—专业IT笔试面试备考平台_牛客网来源：牛客网

时间限制：C/C++ 1 秒，其他语言 2 秒

空间限制：C/C++ 262144K，其他语言 524288K

64bit IO Format: %lld

题目描述

写一个程序来模拟操作系统的进程调度。假设该系统只有一个 CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。

如果一个进程到达的时候 CPU 是空闲的，则它会一直占用 CPU 直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用 CPU，而老的只有等待。

如果一个进程到达时，CPU 正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。一旦 CPU 空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。

输入描述：

输入文件包含若干行，每一行有四个自然数（均不超过 108），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。

输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过 15000 个。

输出描述：

按照进程结束的时间输出每个进程的进程号和结束时间

示例 1

输入

复制 1 1 5 3 2 10 5 1 3 12 7 2 4 20 2 3 5 21 9 4 6 22 2 4 7 23 5 2 8 24 2 4

1 1 5 3

2 10 5 1

3 12 7 2

4 20 2 3

5 21 9 4

6 22 2 4

7 23 5 2

8 24 2 4

输出

复制 1 6 3 19 5 30 6 32 8 34 4 35 7 40 2 42

1 6

3 19

5 30

6 32

8 34

4 35

7 40

2 42

宏观思维，未处理的集合，已经处理完毕的集合。

定义 pq 优先队列存储 cpu 待处理的进程集合。

定义 waiting 存储还没有到达的进程集合。

如果 waiting 集合为空集，pq 优先队列依次处理即可。所以我们的目标可以是将还没有到达的进程集合变为空集。

定义 now_time 表示现在的时间。

现在的时间，到下一个进程到达的时间，这段时间内 cpu 可以一直工作。

这时有两种情况，第一种情况，当前进程处理完了，下一个进程还没到。

第二种情况，当前进程还没处理完，下一个进程就到了。

#include <bits/stdc++.h>
using namespace std;

class process {
public:
    int id;         // 进程ID
    int start_time; // 开始时间
    int life;       // 生命周期
    int priority;   // 优先级


    process(int id_, int start_time_, int life_, int priority_)
        : id(id_), start_time(start_time_), life(life_), priority(priority_) {}


    bool operator<(const process& p) const {
        if (priority == p.priority)
            return start_time > p.start_time;
        return priority < p.priority;
    }
};

int main() {
    priority_queue<process> pq;
    vector<process> waiting;

    int id, start_time, life, priority;
    while (cin >> id >> start_time >> life >> priority) {
        waiting.push_back(process(id, start_time, life, priority));
    }

    int now_time = 0;
    int index = 0;

    while (index < waiting.size() || !pq.empty()) {

        while (index < waiting.size() && waiting[index].start_time <= now_time) {
            pq.push(waiting[index]);
            index++;
        }

        if (!pq.empty()) {
            process current = pq.top();
            pq.pop();
            int next_arrival_time = (index < waiting.size()) ? waiting[index].start_time : INT_MAX;
            int execute_time = min(current.life, next_arrival_time - now_time);
            now_time += execute_time;
            current.life -= execute_time;
            if (current.life == 0) {
                cout << current.id << " " << now_time << endl;
            } else {
                pq.push(current);
            }
        } else {

            now_time = waiting[index].start_time;
        }
    }

    return 0;
}

优先队列自定义类型

在 C++中，自定义类型的优先队列可以通过使用std::priority_queue结构实现，它是 C++标准库中的一部分。为了让std::priority_queue支持自定义类型，您需要定义比较方式，这通常通过重载运算符或提供自定义比较函数（比如函数对象）来完成。下面，我将给出两种方法来实现带有自定义类型的优先队列。

方法 1：重载<运算符

如果您的自定义类型可以自然地定义一个“小于”关系，则可以通过重载<运算符来实现比较逻辑。std::priority_queue默认使用std::less作为比较方式，这意味着元素将按照从大到小的顺序排序（即最大元素位于队列前端）。

重载<运算符的意义是判断前者是否是小于后者。

#include <iostream>
#include <queue>

class MyObject {
public:
    int value;
    MyObject(int val) : value(val) {}

    // 重载<运算符
    bool operator<(const MyObject& other) const {
        return value < other.value; // 更大的值具有更高的优先级
    }
};

int main() {
    std::priority_queue<MyObject> myQueue;

    myQueue.push(MyObject(10));
    myQueue.push(MyObject(5));
    myQueue.push(MyObject(20));

    while (!myQueue.empty()) {
        MyObject obj = myQueue.top();
        std::cout << obj.value << std::endl;
        myQueue.pop();
    }

    return 0;
}

方法 2：使用自定义比较函数

如果您不想或不能修改自定义类型来重载运算符，或者需要在不同的情况下使用不同的排序准则，您可以通过定义一个比较函数对象来实现。

std::priority_queue<MyObject, std::vector<MyObject>, CompareMyObject> myQueue;

优先队列底层是堆，中间都是用 vector<自定义类型>作为容器即可。

第三个位置填写自定义比较的类。

自定义比较的类重载的是（）。

#include <iostream>
#include <queue>
#include <vector>

class MyObject {
public:
    int value;
    MyObject(int val) : value(val) {}
};

// 自定义比较函数对象
class CompareMyObject {
public:
    bool operator()(const MyObject& obj1, const MyObject& obj2) {
        return obj1.value < obj2.value; // 更大的值具有更高的优先级
    }
};

int main() {
    std::priority_queue<MyObject, std::vector<MyObject>, CompareMyObject> myQueue;

    myQueue.push(MyObject(10));
    myQueue.push(MyObject(5));
    myQueue.push(MyObject(20));

    while (!myQueue.empty()) {
        MyObject obj = myQueue.top();
        std::cout << obj.value << std::endl;
        myQueue.pop();
    }

    return 0;
}