NOTE
比赛链接：Codeforces Round 1101.(Div. 2)

A - Convegence#

关键词：思维

思路#

一次通话可以同时处理目标位置两侧的两个人，考虑把集合地点选在数组中的中位数。

如果目标位置选为 x，定义：L = 位于 x 左侧的人数，R = 位于 x 右侧的人数，每次通话最多只能处理一名左侧人员，因此至少需要 L 次通话。同理，至少需要 R 次通话。

所以答案至少为 $max(L, R)$ ，为了让这个值尽可能小，需要让目标位置左右两侧的人数尽可能平衡。因此应当选择中位数。

令 $mid=a[n/2]$ ，最终要让所有人都移动到 $mid$ ，考虑严格小于 $mid$ 和严格大于 $mid$ 的人数，取二者最大值即可。

Code#

1
// Problem: CF 2232 A
2
// Contest: Codeforces - Codeforces Round 1101 (Div. 2)
3
// URL: https://codeforces.com/contest/2232/problem/A
4
// Time: 2026-05-30 22:35:30
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    ll n;
29
    cin >> n;
30

31
    vector<ll> a(n);
32

33
    for (int i = 0; i < n; i++)
34
        cin >> a[i];
35

36
    sort(all(a));
37

38
    ll mid = a[n / 2];
39
    ll l = lower_bound(all(a), mid) - a.begin(), r = a.end() - upper_bound(all(a), mid);
40
    cout << max(l, r) << endl;
41
}
42

43
int main()
44
{
45
    fastio();
46

47
    int T = 1;
48
    cin >> T;
49

50
    while (T--)
51
        solve();
52

53
    return 0;
54
}

B - Cake Leveling#

关键词：思维，前缀约束

思路#

对于每一个前缀 $a[1...i]$ ，求一个最大的整数高度 $h$ ，使得用高度为 $h$ 的刀从左向右扫过之后，前 $i$ 个位置的糖霜能够全部保持在同一高度。前方位置高于 $h$ 的部分会被推向下一个位置。

假设我们正在处理长度为 $i$ 的前缀： $a_1, a_2,\cdots, a_i$ ，记前缀和为 $S$ ，对于任意前 $k$ 个位置，它们至少需要有 $k \times h$ 个单位的糖霜。因此必须满足 $S \ge k \times h$ ，这个条件需要对所有前缀同时成立，也就是说，前 $i$ 个位置可以达到的最大高度为 $ans_i = \min\left(\left\lfloor \frac{S_1}{1} \right\rfloor, \left\lfloor \frac{S_2}{2} \right\rfloor, \ldots, \left\lfloor \frac{S_i}{i} \right\rfloor\right)$ 。每加入一个新元素，需要计算当前前缀的平均值向下取整，并维护历史最小值。

Code#

1
// Problem: CF 2232 B
2
// Contest: Codeforces - Codeforces Round 1101 (Div. 2)
3
// URL: https://codeforces.com/contest/2232/problem/B
4
// Time: 2026-05-30 22:48:22
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    ll s = 0, res = 1e18;
32

33
    for (ll i = 1, x; i <= n; i++)
34
    {
35
        cin >> x;
36

37
        s += x;
38
        res = min(res, s / i);
39
        cout << res << " ";
40
    }
41
    cout << endl;
42
}
43

44
int main()
45
{
46
    fastio();
47

48
    int T = 1;
49
    cin >> T;
50

51
    while (T--)
52
        solve();
53

54
    return 0;
55
}

C - Seating Arrangement#

关键词：反悔贪心

思路#

题意简述：有 $n$ 个朋友， $x$ 张桌子，每张桌子 $s$ 个座位，有三种朋友： $I$ 必须坐在空桌， $E$ 必须坐在非空桌， $A$ 可以坐在任何桌。需要按顺序分配座位，可以拒绝某个朋友入座，希望最后留下的朋友尽可能多。

考虑如何表示不同状态的桌子#

一共有 $m$ 张桌子，每张桌子有 $k$ 个座位。我们将已经坐过人的桌子称作“已启用桌子”。

假设当前启用了 $cntm$ 张桌子，那么这些桌子的总容量为 $cntm \times k$ ，如果当前已经入座 $sum$ 个人，那么仍然可以坐在非空桌上的人数为 $cntm \times k - sum$ ，因此要判断是否还有非空但还没坐满的桌子，只需要判断 $sum+1 \le cntm \times k$ ，不需要记录每张桌子分别坐了多少人。

考虑如何安排三类人#

$I$ :必须新开一张桌，只要满足 $cntm <m$ 就可以直接让他入座；如果所有桌子都已经启用，则当前的 $I$ 只能离开。

1
cntm++, sum++;

$E$ ：只能使用已有桌子的容量，如果 $sum+1 \le cntm \times k$ ，说明当前已启用的桌子里面还有空位，可以直接安排。否则说明所有已启用的桌子都已经坐满。此时 $E$ 不能开新桌，但可以借助 $A$ 。

1
sum++;

$A$ ：万能符，遇到一个 $A$ 时有两种选择，将 $A$ 当作 $I$ 意味着新开一张桌，将 $A$ 当作 $E$ 意味着坐在已有的非空桌。

我们不能看到 $A$ 就贪心地开新桌，原因如下：

考虑 $m=2,k=2$ ，队列为 $AAIE$ 的情况：如果两个 $A$ 优先坐了两张空桌， $I$ 没有位置，最后只能坐 $3$ 个人，但如果第二个 $A$ 坐在第一桌，就能让四个人都坐下。

因此对于 $A$ ，假如当前旧桌还有空位，优先让 $A$ 坐在旧桌；如果旧桌没位置再考虑让 $A$ 开一个新桌。

考虑反悔策略#

考虑 $m=2,k=3$ ，队列为 $AAEE$ 的情况，按照刚刚的贪心策略，桌 $1$ 上有 $A, A, E$ 三个人，桌 $2$ 为空。

但我们重新解释第二个 $A$ 的选择，第二个 $A$ 当时并不是坐在桌 $1$ ，而是坐在桌 $2$ ，最后桌 $1$ 上有 $A, E, E$ ，桌 $2$ 上有 $A$ ，四个人全部入座。

NOTE
算法中的“反悔”不是让某个 $A$ 真的换座，而是：此前不要立即确定 $A$ 的具体座位。当未来出现冲突时，再选择一种更合适的历史解释。

考虑用一个变量 $cntA$ 表示当前还有多少个 $A$ 没有被固定为“开桌者”。这些 $A$ 暂时被视为坐在已有桌子上，但未来仍然可以反悔，将其中一个重新解释为坐在空桌。

1
cntA--, cntm++;
2
// 选一个之前出现的A，将它重新解释为开桌者，并新增一张非空桌，总容量增加k

总结#

1
遇到 I
2
  → 必须开桌
3

4
遇到 E
5
  → 优先坐旧桌
6
  → 如果容量不足，尝试消耗一个旧 A 开桌
7

8
遇到 A
9
  → 优先假装它是 E，坐旧桌
10
  → 保留一张“开桌券”
11
  → 未来必要时，再将它反悔为 I

Code#

1
// Problem: CF 2232 C2
2
// Contest: Codeforces - Codeforces Round 1101 (Div. 2)
3
// URL: https://codeforces.com/contest/2232/problem/C2
4
// Time: 2026-05-31 17:34:28
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    ll table_cnt, seat_cnt;
30
    cin >> n >> table_cnt >> seat_cnt;
31

32
    string u;
33
    cin >> u;
34

35
    ll opened = 0; // 已启用桌子数量
36
    ll seated = 0; // 已入座人数
37
    ll spare_a = 0; // 可以被重新解释为开桌者的 A 数量
38

39
    for (char c: u)
40
    {
41
        if (c == 'I')
42
        {
43
            if (opened < table_cnt)
44
            {
45
                opened++;
46
                seated++;
47
            }
48
            continue;
49
        }
50

51
        if (c == 'A')
52
            spare_a++;
53

54
        if (seated < opened * seat_cnt)
55
            seated++;
56

57
        else if (spare_a > 0 && opened < table_cnt)
58
        {
59
            spare_a--;
60
            opened++;
61
            seated++;
62
        }
63
        else if (c == 'A')
64
            spare_a--;
65
    }
66

67
    cout << seated << endl;
68
}
69

70

71
int main()
72
{
73
    fastio();
74

75
    int T = 1;
76
    cin >> T;
77

78
    while (T--)
79
        solve();
80

81
    return 0;
82
}