1 AC情况
| Convention S | Convention II S | Mooyo Mooyo S |
|---|---|---|
| Accepted \texttt{\color{green}{Accepted}} Accepted | Accepted \texttt{\color{green}{Accepted}} Accepted | Unaccepted \texttt{\color{red}{Unaccepted}} Unaccepted（ Accepted \texttt{\color{green}{Accepted}} Accepted） |
2 题目详情
Convention S
题目描述
N N N 头奶牛，奶牛 i i i 在时刻 t i t_i ti 到达。安排 M M M 辆车，每辆最多能坐 C C C 头奶牛。
安排奶牛乘车。当最后一头乘坐某辆车的奶牛到达的时候，这辆车就可以发车了。如果没有到达，那么其他要乘坐这辆车的奶牛就要等待到发车的时刻。
求等待时间最长的奶牛等待的时间的最小值。
赛时经历
二分，思路正确。但调试时出现了一些细节问题。
题解
等待时间最长的奶牛等待的时间的最小值
经典二分。
#include <bits/stdc++.h>
#define endl '\n'
#define CLOSE ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, m, c, t[N], ans, maxn;
bool check(ll mid) {
ll bus = 0, cnt = t[1], num = 0;
for (int i = 1; i <= n; i++) {
if (num >= c || t[i] - cnt > mid)
bus++, num = 0, cnt = t[i];
num++;
}
bus++;
return (bus <= m);
}
int main() {
CLOSE;
cin >> n >> m >> c;
for (int i = 1; i <= n; i++)
cin >> t[i];
sort(t + 1, t + n + 1);
ll l = 0, r = t[n];
while (l < r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l;
return 0;
}
Convention II S
题目描述
N N N 头牛排队吃草，编号为 i i i 的奶牛来排队的时刻为 a i a_i ai，吃草的时长为 t i t_i ti。
当轮到一头牛吃完草后，会从队伍中选择编号最靠前（最小）的奶牛先吃。
求所有奶牛在队伍里等待时间的最大值。
赛时经历
考场做法和赛后做法基本一致，唯一不同是赛时使用的是set来模拟队伍，稍繁琐一些。
题解
模拟。
首先把这些奶牛按照到达的时间排序，保证时间正确。
对于队伍里的吃草优先级问题，用priority_queue来模拟队伍是最简单的。结构体里面以编号为索引重载运算符。
具体模拟思路见代码。
#include <bits/stdc++.h>
#define endl '\n'
#define CLOSE \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
struct cow {
ll i, a, t;
bool operator<(const cow& x) const { return i > x.i; } //吃草优先级
} a[N];
bool cmp(cow a, cow b) { //到达时间排序
return (a.a < b.a);
}
priority_queue<cow> q; //模拟队伍
int main() {
CLOSE;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].a >> a[i].t, a[i].i = i;
sort(a + 1, a + n + 1, cmp); //按到达时间排序
ll cnt = a[1].a, i = 1, ans = 0;
//i表示前(i-1)头奶牛都进入队伍过了，轮到第i头了；
//cnt表示当前的时刻；
//ans记录答案
while (i <= n || !q.empty()) {
//i <= n说明有奶牛没进过队伍；!q.empty()说明队伍里的奶牛还没有处理完
if (q.empty() && i <= n) //队伍空了，且还有没入队过的，放进去一个
q.push(a[i]), i++;
cow k = q.top(); //取出队头，吃草优先级最大的那头奶牛
q.pop();
while (a[i].a <= (max(cnt, k.a) + k.t) && i <= n)
//如果奶牛i在奶牛k吃完之前（或正好吃完时）到达，把奶牛i放进队伍
q.push(a[i]), i++;
ans = max(ans, cnt - k.a); //ans记录奶牛k等待最大值
cnt = max(cnt, k.a) + k.t; //cnt时间更新
//补充解释一下cnt更新的策略:
//一种情况是奶牛k之前的奶牛用掉的总时长超过了奶牛k的到达时间，应该取更长的时间cnt + k.t
//另一种情况是奶牛k到达时队伍里没有人，取更长的时间k.a + k.t
}
cout << ans;
return 0;
}
Mooyo Mooyo S
题目描述
N N N 行 10 10 10 列的屏幕，其中有类型 1 ∼ 9 1\sim 9 1∼9 的不同类型的干草（每一捆干草占 1 1 1 格，没有干草用 0 0 0 表示)。受重力作用，它们落在所在列的最下面。
相同类型的且相连（上下左右方向相邻) 的若干干草成为一个连通块。如果一个连通块有由不少于 K K K 个干草组成，那么这个连通块可以被消除。消除后剩下的干草又会因为重力下落，它们当中有可能会组成新的可以消除的连通块……循环往复，直到所有干草都无法消除为止。
问最后屏幕的布局。
赛时经历
没有想到连通块在屏幕任何地方都可以删，而是只删了屏幕底下的连通块
没有发现
dfs()代码的隐藏漏洞，还是样例造的不够好void dfs(int x, int y, char c, bool flag) { if (x < 1 || y < 1 || x > n || y > 10 || s[x][y] != c || vis[x][y]) return; vis[x][y] = 1; cnt++; dfs(x - 1, y, c, flag); dfs(x + 1, y, c, flag); dfs(x, y - 1, c, flag); dfs(x, y + 1, c, flag); if (flag) vis[x][y] = 0; }这是赛时的
dfs()代码，该代码希望在flag为true时用cnt来统计连通块内干草的数量。看起来思路没有错误，样例也没有问题，但在大测试点下很容易地出现了纰漏。思考一个简单的矩形连通块:
11 11很显然，从左上开始，进行
dfs(左上)，然后进入dfs(左下)，接着到dfs(右下)，最后是dfs(右上)，cnt增加到了 4 4 4，然后最终回溯到了dfs(左上)。这一次搜索到这里就应该结束了。但是，在回溯过程中vis标记数组又还原成了 0 0 0，这看似合乎寻常，但其中隐藏着巨大的缺陷——那就是回溯到dfs(左上)后不知道右上已经被搜过了，又进入了dfs(右上)，然后依次是dfs(右下)、dfs(左下)，cnt增加到了 7 7 7 才停止。所以，这段代码的漏洞就在于，
vis没有标记好搜索路线，因为迅速更新覆盖了搜索路径痕迹，导致出现多次访问。
题解
模拟。
dfs()：统计连通块干草数量。为了保证记录不重复，我们不对vis数组进行还原操作。
void dfs(int x, int y, char c) {
if (x < 1 || y < 1 || x > n || y > 10 || s[x][y] != c || vis[x][y])
return;
vis[x][y] = 1;
cnt++;
dfs(x - 1, y, c);
dfs(x + 1, y, c);
dfs(x, y - 1, c);
dfs(x, y + 1, c);
}
recover()：如果连通块干草数量少于 K K K 个，执行此操作。此函数会把先前dfs()的搜索痕迹删除掉，即还原vis数组。没有被还原的vis数组标记的地方视为要删除的干草位置。
void recover(int x, int y, char c) {
if (x < 1 || y < 1 || x > n || y > 10 || s[x][y] != c || !vis[x][y])
return;
vis[x][y] = 0;
recover(x - 1, y, c);
recover(x + 1, y, c);
recover(x, y - 1, c);
recover(x, y + 1, c);
}
organize()：搜索并标记完所有需要删除的连通块后执行此操作。它将删除vis数组标记的位置的干草，并整理屏幕。
void organize() {
queue<char> q; //q保存的是每一列没有删除的干草
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 10; j++)
if (vis[i][j])
s[i][j] = '0'; //删除被vis标记的干草
for (int i = 1; i <= 10; i++) {
for (int j = n; j >= 1; j--)
if (s[j][i] != '0')
q.push(s[j][i]); //如果还有干草，放到q里准备下落
for (int j = n; j >= 1; j--) {
if (!q.empty())
s[j][i] = q.front(), q.pop(); //把q.top()干草下落到底部
else
s[j][i] = '0'; //下落完了，更新旧屏幕单元格
}
}
memset(vis, 0, sizeof vis); //重置vis数组
}
主函数main()：不断重复搜索连通块、标记可删除连通块、整理屏幕过程，知道无可删除连通块为止。
int main() {
CLOSE;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> s[i], s[i] = " " + s[i];
int flag = 1;
while (flag) {
flag = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 10; j++) {
if (s[i][j] == '0' || vis[i][j]) //如果是空白单元格或者已经被标记过了，无需搜索
continue;
cnt = 0;
dfs(i, j, s[i][j]); //搜索
if (cnt < k) { //清除搜索区域痕迹
recover(i, j, s[i][j]);
} else {
flag = 1; //有可以删除的连通块，标记
}
}
}
organize(); //整理屏幕
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 10; j++)
cout << s[i][j];
cout << endl;
}
return 0;
}
![P2676 [<span style='color:red;'>USACO</span>07<span style='color:red;'>DEC</span>] Bookshelf B](https://img-blog.csdnimg.cn/direct/3711ee9adf52433b9f2e0b194a57c953.png#pic_center)
