L1-049 天梯赛座位分配
题目 L1-049 天梯赛座位分配
思路分析
三个学校 分别有 3 4 2个队伍 首先初始化第一轮的排座 学校1的第一个学生坐1 学校2 的第一个学生坐2 学校三的第一个学生坐3 然后找到最少队伍的那个学校 有两个队伍 那就是可以以3为循环 安排到第 60号位置（分别在三个学校做等差数列） 学校一 首项为1 公差为3 推到60 得：1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 学校二：首项为2 公差为3 推到60 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 学校三：首项为3 公差为3 推到60 得3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 用优先队列或者有序set维护这个队伍 方便取出最大的作为下一轮的首项（第一轮也适用 因为123是事先填入的） 然后所有学校减去2个队伍（已经安排完） 还剩2个学校 分别为1 2个队伍 取到最少的1 乘上n(2) 得到20 60+20=80 那么继续往后推到第80个座位 学校一： 以上次安排完的最后一个位置开始 第61 公差为2 推到80 61 63 65 67 69 71 73 75 77 79 学校二：62 64 66 68 70 72 74 76 78 80 再减去10 还剩学校2有一个队伍 以公差为2做 到结束 82 84 86 88 90 92 94 96 98 100
代码实现
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using Pll = pair<ll, ll>;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };h
const int inf = 0x3f3f3f3f;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
// 读入每所高校的队伍数，并初始化 st 向量
for (int i = 1; i <= n; i++) {
cin >> m[i];
st.push_back({i, m[i]});
}
// 按照队伍数从小到大排序（用于后续动态更新队伍最少的学校）
sort(st.begin(), st.end(), [](pai a, pai b) {
return a.second < b.second;
});
// 对每一所学校 i，输出它的所有队伍安排
for (int i = 1; i <= n; i++) {
cout << "#" << i << endl;
int id = i; // 当前学校起始编号为 i，初始的首项
int k = n; // 当前还没排完的高校数量，初始为 n
int v = 0; // 指向 st 中下一个队伍排完的学校
int dt = (n == 1) ? 2 : n; // 初始化公差，如果只有一所学校，公差为 2 否则为 n
// 安排第 i 所高校的所有队伍
for (int x = 1; x <= m[i]; x++) {
// 每支队伍安排 10 个人
for (int j = 1; j <= 10; j++) {
cout << id;
if (j != 10) cout << ' ';
else puts("");
id += dt; // 更新座位号，等差
}
// 检查是否有其他学校的队伍刚好也排完了（x == st[v].second）
while (v < st.size() && x == st[v].second) {
k--; // 一个学校排完，未完成的学校数减少
// 如果剩下不只当前学校，且当前学校编号在排完的学校之后，需要回退 1 位首项
// 这是为了防止座位冲突，确保后续等差排布不重叠
if (k != 1 && st[v].first < i)
id--;
v++;
}
// 更新新的公差
dt = (k == 1) ? 2 : k;
}
}
return 0;
}
同类题型
视频讲解
⬅️ L1-048 矩阵A乘以B 🏠 00-天梯赛 ➡️ L1-050 倒数第N个字符串
💬 评论