刚打完ABC接着要打div2，看到第一题第一时间没想过来就不打算下场了，后续补题发现，其实前三题都比较简单

补题

A

题面

爱丽丝邀请她的朋友参加一个聚会吃蛋糕。然而，每个朋友可能不在同一个地方，所以大家必须先在同一个地点见面。

Alice 有 nn 个朋友，其中第 ii 个朋友位于位置 aia_i 。为了让每个人都在同一个地方，Alice 必须进行多次群组通话。不幸的是，信号很弱，Alice 一次只能呼叫 22 其他人。

作为一个好人，爱丽丝不希望她的朋友走太远。因此，对于包含第 ii 个朋友和第 jj 个朋友的每个群组通话，Alice 会告诉他们两个在 min⁡(ai,aj)\min(a_i, a_j) 和 max⁡(ai,aj)\max(a_i, a_j) （含）之间的某个整数位置见面。之后，他们两人都会快速移动到该位置，以至于Alice在移动过程中无法进行任何群组通话。请注意，一旦这些朋友到达该位置，爱丽丝就可以再次呼叫他们。

聚会即将开始，Alice 需要快速进行群组通话。帮助她找到需要拨打的最少群组通话次数。

思路:

要将所有人聚在一起，而朋友ii和朋友jj可以通过一次操作瞬移到两人之间的某个位置，即AiA_i和AjA_j之间的任意一个位置。那么我们将AA排序，将最远的两人往中间瞬移，不断操作，直至所有人都到一起为止。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void sol()
{
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+N+1);
    int ans=0;
    int l=1,r=N;
    while(a[l]!=a[r])
    {
        ans++;
        l++;
        r--;
        if(l>N/2)break;
    }
    cout<<ans<<'\n';
}

B

题面

爱丽丝正在为她的聚会准备蛋糕。然而，她太匆忙了，所以蛋糕上的糖霜不均匀。为了快速解决这个问题，爱丽丝会将她的刀放在某个整数高度，然后从左到右扫过糖霜以使糖霜平整。

正式地，令 aia_i 为第 ii 个位置处的糖霜高度。假设爱丽丝将她的刀放在某个整数高度 hh 。如果位置 ii 处的糖霜高度大于 hh ，则多余的糖霜将被推至位置 i+1i + 1 。 nn 位置上多余的糖霜将完全从蛋糕上脱落。

爱丽丝和她的朋友们非常喜欢蛋糕糖霜。由于 Alice 可能决定提供蛋糕的某些前缀而不是整个蛋糕，因此请帮助她找到糖霜的最大高度，同时保持 i=1,2,…,ni = 1, 2, \ldots, n 的前 ii 位置的糖霜水平。

分析:

假设取出前ii个糖霜用刀扫平后最大高度为hh，那么处理前i+1i+1个糖霜时：

  • 如果Ai+1>AiA_{i+1}>A_i，那么Ai+1A_{i+1}必须被抹平到hh。
  • 如果Ai+1≤AiA_{i+1}\le A_i，那么就可以将前面的蛋糕平摊给Ai+1A_{i+1}，此时h′=⌊∑1i+1Aki+1⌋h'=\lfloor\frac{\sum\limits _{1}^{i+1}A_k}{i+1}\rfloor，多余的被丢弃。

由此也可以发现最后的答案一定是个非递增序列。

思路：

只需要维护一个前缀和sumsum，如果加上AiA_i后，均值⌊sumi⌋\lfloor\frac{sum}{i}\rfloor增大，则答案不变，反之答案变小，因此每次取ansi=min⁡(ansi−1,⌊sumi⌋)ans_i=\min(ans_{i-1},\lfloor\frac{sum}{i}\rfloor)即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void sol()
{
    int n;
    cin>>n;
    int sum=0,ans=MAX;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        ans=min(ans,sum/i);
        cout<<ans<<' ';
    }
    cout<<'\n';
}

C

题面

爱丽丝的朋友们来参加聚会了，现在他们正在排队参加聚会。

聚会上有 xx 张桌子，每张桌子有 ss 个座位。每个座位只能容纳一个人。

每个朋友都具有以下三种性格之一：

  • 必须坐在空桌子旁的内向者 (I)
  • 必须坐在非空桌子旁的外向者 (E)
  • 中间性格者 (A) 可以坐在任何桌子上。

最初，每个座位都是空的。然而，由于爱丽丝正在吃蛋糕，她的朋友们已经排好了队，爱丽丝无法改变他们的顺序。对于队列中的每个人，爱丽丝必须为他们分配一张桌子或将他们踢出队伍。每个人就座后，下一个人就被分配到一张桌子。

为了在聚会上玩得开心，爱丽丝需要在聚会上容纳尽可能多的人。帮助她找到参加聚会的最多朋友数量。

请注意，一旦朋友入座，即使不再按照其性格入座，也不得再移动。

分析:

由于排队顺序无法改变，而每个人权重相同，不分贵贱，因此我们依次贪心地处理每个人，能入座就入座，并且在一定情况下，我们可以通过合理修改已入座人的位置，从而让更多地人入座。（反悔贪心）

  1. 对于A人，他可以随便坐，因此我们就要安排他入座，哪怕后续导致I人实在无法入座，但由于均只对贡献了1，我们可以舍弃这个I人。
    • A人无法入座的唯一条件就是彻底坐满了人。
  2. 对于E人，他必须坐在有人的桌子上。那么他需要有A人或I人为他“开辟”一张桌子，才能入座。
    • E人无法入座的条件为已有人的桌子坐满了人且没有足够的A人和I人为他开辟桌子。
  3. 对于I人，他必须坐在没有人的桌子上。因此我们需要尽量让A人和E人占据的桌子更少，从而让I人入座。
    • I人无法入座的条件为没有无人桌子。（在A人和E人占据最少桌子时）

思路：

通过以上分析，我们需要统计入座人数sumsum。
因为E人入座需要判断是否有足够多的A人和I人，因此我们要统计入座A人数sumAsumA，入座I人数sumEsumE。（当然二者可以合并）
我们需要尽可能压缩A人和E人的空间，因此我们一个桌子一个桌子地处理，只有在必要情况下我们才去开辟下一个桌子，记录坐到了第icnticnt个桌子。
由此我们可以知道有人桌子中最多可以坐icnt×sicnt\times s个人。
最多可以开辟sumA+sumIsumA+sumI张桌子。
再结合上述贪心思想，便可以通关本题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void sol()
{
    int n,x,s;
    cin>>n>>x>>s;
    int icnt=0;
    string S;
    cin>>S;
    int sum=0,sumA=0,sumI=0;
    for(auto i=0u;i<S.size();i++)
    {
        char c=S[i];
        if(c=='A')
        {
            if(icnt*s>sum)
            {
                sumA++;
                sum++;
            }
            else
            {
                if(icnt<x)
                {
                    sumA++;
                    sum++;
                    icnt++;
                }
            }
        }
        if(c=='E')
        {
            if(icnt*s>sum)
            {
                sum++;
            }
            else
            {
                if(icnt<x&&sumA+sumI>icnt)
                {
                    icnt++;
                    sum++;
                }
            }
        }
        if(c=='I')
        {
            if(icnt<x)
            {
                icnt++;
                sumI++;
                sum++;
            }
        }
    }
    cout<<sum<<'\n';
}