代码思路：
- 初始化圈：利用
std::list保存编号为 1 到 n 的人。 - 循环报数：利用迭代器模拟报数的过程，每次数到 m 时将对应的人出圈。
- 循环处理：
std::list::erase删除出圈的人，并返回下一个人的迭代器，若迭代器越界则重新从头开始。 - 输出结果：记录并输出所有出圈人的编号。
#include <iostream>
#include <list> // 用于存储和操作循环链表
#include <vector> // 用于保存出圈顺序的结果
using namespace std;
int main() {
int n, m;
cin >> n >> m; // 输入 n 人数，m 报数上限
// 1. 初始化环（使用 list 容器）
list<int> circle;
for (int i = 1; i <= n; ++i) {
circle.push_back(i); // 将编号 1 到 n 的人加入列表
}
// 2. 准备迭代器指向当前报数位置
auto it = circle.begin();
vector<int> result; // 用于存储出圈顺序
// 3. 模拟报数直到所有人出圈
while (!circle.empty()) {
// 从当前迭代器位置开始数到第 m 个人
for (int i = 1; i < m; ++i) {
++it; // 移动迭代器到下一个人
if (it == circle.end()) {
it = circle.begin(); // 如果到达列表尾部，则回到头部
}
}
// 4. 记录数到 m 的人，并从列表中删除
result.push_back(*it); // 保存当前出圈人的编号
it = circle.erase(it); // 删除当前编号，并返回下一个位置的迭代器
if (it == circle.end()) {
it = circle.begin(); // 若删除后迭代器越界，则回到列表开头
}
}
// 5. 输出结果
for (size_t i = 0; i < result.size(); ++i) {
cout << result[i]; // 输出每个出圈人的编号
if (i != result.size() - 1) { // 控制输出格式，避免最后一个编号后有空格
cout << " ";
}
}
cout << endl;
return 0;
}
详细解读
初始化环
- 使用
std::list创建一个循环链表，适合频繁的插入和删除操作。 - 编号从 1 到 n 加入列表，表示 n 个人围成一圈。
模拟报数
-
从指定位置开始报数：
- 使用迭代器
it表示当前报数的人。 - 每次移动迭代器 m−1 次找到第 m 个人。若到达列表尾部，则回到头部 (
circle.begin())，模拟环形报数。
- 使用迭代器
-
删除数到 mmm 的人：
circle.erase(it)删除当前迭代器指向的元素，并返回下一个有效迭代器。- 若删除的元素是最后一个，则重新从列表头部开始。
存储和输出结果
- 每次删除时，将出圈人的编号加入
result向量。 - 最后按照题目要求，输出出圈编号，编号之间用空格隔开。
解题思路
-
后缀表达式的特点：
- 操作数直接入栈。
- 遇到运算符时，从栈中取出两个操作数，进行运算，结果再入栈。
- 最后栈中只剩下一个元素，即为表达式的结果。
-
输入解析：
- 操作数以
.分隔。 - 运算符为
+ - * /。 - 结束符号为
@，标志表达式结束。
- 操作数以
-
处理规则：
- 向 0 取整：对于
/运算，C++ 中的/符号自动实现了向 0 取整，因此无需额外处理。
- 向 0 取整：对于
#include <iostream>
#include <stack> // 使用栈存储和处理操作数
#include <string> // 用于处理字符串
using namespace std;
int main() {
string s;
cin >> s; // 输入后缀表达式字符串
stack<int> stk; // 定义一个栈，用于存储操作数
int i = 0; // 用于遍历字符串的索引
while (s[i] != '@') { // 遍历整个字符串，直到遇到结束符号 '@'
if (isdigit(s[i])) { // 检查当前字符是否是数字
int num = 0; // 用于保存完整的操作数
while (isdigit(s[i])) { // 当连续的字符是数字时，解析完整的操作数
num = num * 10 + (s[i] - '0'); // 构造数字，字符转换为整数
i++; // 移动到下一个字符
}
stk.push(num); // 将完整的操作数压入栈
} else if (s[i] == '.') {
// 遇到数字结束符 '.'，直接跳过
i++;
} else {
// 当前字符是运算符，开始运算
// 从栈中弹出两个操作数（注意先后顺序）
int b = stk.top(); // 先弹出的是右操作数
stk.pop(); // 删除栈顶元素
int a = stk.top(); // 再弹出的是左操作数
stk.pop(); // 删除栈顶元素
int result = 0; // 用于保存运算结果
if (s[i] == '+') {
result = a + b; // 加法运算
} else if (s[i] == '-') {
result = a - b; // 减法运算
} else if (s[i] == '*') {
result = a * b; // 乘法运算
} else if (s[i] == '/') {
result = a / b; // 除法运算（向 0 取整，由 C++ 自动实现）
}
stk.push(result); // 将运算结果压入栈
i++; // 移动到下一个字符
}
}
// 栈中只剩下一个元素，即为表达式的最终结果
cout << stk.top() << endl; // 输出结果
return 0; // 程序结束
}
逻辑：我们可以使用set储存当前位置前面所有元素，并自动排序。然后我们需要找到大于等于当前元素的位置和他的前一个位置（刚好小于当前元素），再取这两个元素分别与当前元素相减的绝对值的较小的一个作为他的最小波动值。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set<int> s; // 用于动态维护已排序的营业额集合
set<int>::iterator k, a; // 迭代器，用于定位最近的上下界
int n, x, ans = 0; // n: 天数, x: 当前营业额, ans: 最小波动值总和
int main() {
// 插入哨兵值，避免越界问题
s.insert(192608170); // 极大值哨兵
s.insert(-192608170); // 极小值哨兵
// 读取天数
scanf("%d", &n);
// 遍历每一天的营业额
for (register int i = 1; i <= n; ++i) {
// 读取当天营业额
scanf("%d", &x);
// 特殊处理第一天（集合只包含哨兵时）
if (s.size() == 2) {
ans += x; // 第一天的最小波动值直接为当天营业额
s.insert(x); // 将当天营业额插入集合
}
else {
// 查找第一个 >= x 的元素的迭代器
k = s.lower_bound(x);
// 如果当前值不存在于集合中，计算波动值并插入
if (*k != x) {
// 找到比 x 小的最大值的迭代器
a = k;
a--; // 前移迭代器，获取下界
// 计算波动值：min(|*a - x|, |*k - x|)
ans += min(abs(*a - x), abs(*k - x));
// 插入当天营业额到集合
s.insert(x);
}
}
}
// 输出最终结果
printf("%d\n", ans);
return 0;
}
register int 是 C++ 中的一个变量声明修饰符，其中 register 用来建议编译器将变量存储在 CPU 寄存器中，而不是在内存中，以提高访问速度。
我们可以把每相邻的的两个同学想象成他们牵着手（如图）
然后经过换手打到插入的效果
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int mx = 1e5 + 10; // 最大的同学数量
int n, m; // n 是同学的总数，m 是需要删除的同学数量
// 定义一个结构体 T，用于表示每个同学的队列关系
struct T {
int l, r; // 每个同学的左右“手”，即指向左边和右边同学的编号
int d; // d 为 1 时，表示该同学不需要输出，默认为 0 表示需要输出
} t[mx] = {0}; // 初始化所有同学的关系和标记
// add 函数：用于将第 k 个同学插入到队列中的第 i 个同学的左边或右边
void add(int i, int k, int f) {
if (f == 1) { // f == 1 表示插入到第 i 同学的右边
t[k].r = t[i].r; // k 同学的右边是 i 同学右边的同学
t[k].l = i; // k 同学的左边是 i 同学
t[i].r = k; // i 同学的右边是 k 同学
t[t[k].r].l = k; // k 同学右边的同学的左边是 k
}
else { // f == 0 表示插入到第 i 同学的左边
t[k].r = i; // k 同学的右边是 i 同学
t[k].l = t[i].l; // k 同学的左边是 i 同学左边的同学
t[i].l = k; // i 同学的左边是 k 同学
t[t[k].l].r = k; // k 同学左边的同学的右边是 k
}
}
int main() {
int x, k, f;
cin >> n; // 输入同学的总数
// 初始化队列，t[0] 表示队列的虚拟头结点
t[0].r = 0;
t[0].l = 0;
// 将第一个同学插入队列中（通过 add 函数）
add(0, 1, 1); // 将 1 号同学插入到 0 号同学的右边
// 处理每个同学的入队操作
for (int i = 2; i <= n; i++) { // 从 2 到 n 号同学
cin >> x >> f; // 输入插入的位置（x 号同学）和插入方向（f：0 表示左，1 表示右）
add(x, i, f); // 将 i 号同学插入到 x 号同学的左边或右边
}
cin >> m; // 输入需要删除的同学数量
// 处理删除操作
while (m--) {
cin >> x; // 输入要删除的同学编号
t[x].d = 1; // 将该同学标记为不输出
}
// 输出队列中未被删除的同学
for (int i = t[0].r; i; i = t[i].r) { // 从队列的第一个同学开始遍历
if (t[i].d == 0) // 如果该同学未被删除（d == 0）
cout << i << " "; // 输出该同学的编号
}
return 0;
}
