堆蛋糕

GitHub跳转原题关系图返回列表

贪心算法:使用出现次数桶和三个单调下降指针,每次取剩余数量最多的三种半径各减一,直到无法再取齐三种半径为止。

OJ: roj

题目 ID: 5010

难度:提高+/省选-

标签:贪心三指针桶排序

创建: 2024-10-18 10:00

更新: 2024-10-18 10:00

形式化题目

给定 nn 个圆柱状蛋糕,每个蛋糕有半径 RiR_i。我们需要尽可能多地组成“三层蛋糕”。 每组成一个三层蛋糕,需要消耗 33 个半径严格递增的蛋糕。 问最多可以组成多少个三层蛋糕?

正解

思路

这道题可以使用贪心的思想:为了尽可能多地组合出三层蛋糕,我们每次组装时,应该优先选择剩余数量最多的那些半径的蛋糕。

如果我们总是从剩余数量前三大(不同半径种类)的蛋糕中各取一个来组成三层蛋糕,是否一定最优呢?可以通过交换论证证明:总是取数量最多的不仅能够避免“数量多但半径不匹配”导致最终剩下大量同一种类的蛋糕,并且等价于在保证合法性前提下的最优化策略(类似 Hall 定理推导出的结论)。

为了快速进行“取剩余数量最大的三种半径”,我们可以进行如下优化:

  1. 统计出现次数:使用 cnt[r] 记录半径为 r 的蛋糕有多少个。
  2. 频率桶排序(桶的桶):使用 bucket[k] 记录“出现次数恰好为 k 的蛋糕半径”有几种。
  3. 三指针下降:使用三个指针 x,y,zx, y, z 在 bucket 数组上从大到小扫描。因为在不断取蛋糕的过程中,某一种半径剩余的个数只会减少(比如从 kk 变到 k−1k-1),所以指针总体上只会递减。 每一轮:
  • 指针 xx 找到一个 bucket[x] > 0,拿走一种半径的一个蛋糕,bucket[x]--;
  • 指针 yy 找到一个 bucket[y] > 0,拿走另一种半径的一个蛋糕,bucket[y]--;
  • 指针 zz 找到一个 bucket[z] > 0,拿走第三种半径的一个蛋糕,bucket[z]--。
  • 然后分别将拿走的这三种半径的剩余数量(即 x−1,y−1,z−1x-1, y-1, z-1)放回到对应的桶中(如果大于 00 的话)。

直到某一次取数时,至少有一个指针找不到大于 00 的桶(说明剩余的不同半径种类不足 33 种),流程结束。

代码

python
import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    
    cnt = [0] * (max(n, 3000000) + 5)
    mxR = 0
    for i in range(1, n + 1):
        r = int(input_data[i])
        cnt[r] += 1
        if r > mxR:
            mxR = r
            
    lim = max(n, mxR)
    mx = 0
    for r in range(1, lim + 1):
        if cnt[r] > mx:
            mx = cnt[r]
            
    bucket = [0] * (mx + 5)
    for r in range(1, lim + 1):
        if cnt[r] > 0:
            bucket[cnt[r]] += 1
            
    ans = 0
    x, y, z = mx, mx, mx
    
    while True:
        while x > 0 and bucket[x] == 0:
            x -= 1
        if x == 0:
            break
        bucket[x] -= 1
        
        while y > 0 and bucket[y] == 0:
            y -= 1
        if y == 0:
            break
        bucket[y] -= 1
        
        while z > 0 and bucket[z] == 0:
            z -= 1
        if z == 0:
            break
        bucket[z] -= 1
        
        if x > 1:
            bucket[x - 1] += 1
        if y > 1:
            bucket[y - 1] += 1
        if z > 1:
            bucket[z - 1] += 1
            
        ans += 1
        
    print(ans)

if __name__ == '__main__':
    solve()
cpp
#include <iostream>
#include <vector>

using namespace std;

const int MAXV = 3000006;
int cnt[MAXV];
int bucket[MAXV + 8];

inline int readInt() {
    int c = getchar_unlocked();
    while (c != '-' && (c < '0' || c > '9')) {
        if (c == -1) return 0;
        c = getchar_unlocked();
    }
    int sgn = 1;
    if (c == '-') { sgn = -1; c = getchar_unlocked(); }
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar_unlocked();
    }
    return x * sgn;
}

int main() {
    int n = readInt();
    if (n == 0) return 0;
    int mxR = 0;
    for (int i = 0; i < n; ++i) {
        int r = readInt();
        ++cnt[r];
        if (r > mxR) mxR = r;
    }
    int lim = n > mxR ? n : mxR;
    int mx = 0;
    for (int r = 1; r <= lim; ++r) {
        if (cnt[r]) {
            ++bucket[cnt[r]];
            if (cnt[r] > mx) mx = cnt[r];
        }
    }
    
    int x = mx, y = mx, z = mx;
    long long ans = 0;
    while (x > 0 && y > 0 && z > 0) {
        while (x > 0 && bucket[x] == 0) --x;
        if (x == 0) break;
        --bucket[x];
        
        while (y > 0 && bucket[y] == 0) --y;
        if (y == 0) break;
        --bucket[y];
        
        while (z > 0 && bucket[z] == 0) --z;
        if (z == 0) break;
        --bucket[z];
        
        if (x > 1) ++bucket[x - 1];
        if (y > 1) ++bucket[y - 1];
        if (z > 1) ++bucket[z - 1];
        ++ans;
    }
    cout << ans << "\n";
    return 0;
}

复杂度

  • 时间复杂度:读入需要 O(n)O(n)。指针 x,y,zx, y, z 是单调不增的,最大值是最高频次(≤n\le n),即便在每一轮中回填较小的频次,但因为每一轮都消耗 33 个蛋糕并且每次扫描非空桶,总体指针移动和桶的增减操作时间均摊也是 O(n)O(n) 级别的。总时间复杂度 O(n)O(n)。
  • 空间复杂度:需要 cnt 和 bucket 两个大小约为 O(max⁡(n,Ri))O(\max(n, R_i)) 的数组。题目数据范围 Ri≤n≤3,000,000R_i \le n \le 3,000,000,数组消耗极少内存。空间复杂度为 O(n)O(n)。

总结

本题通过“每次贪心选择剩余数量最多的三个不同元素”可以得到最优解。利用“频次桶+下降指针”的技巧可以将这个选择过程优化至 O(n)O(n)。值得注意的是,为了避免使用同一个元素,在寻找完前三个后,要“延后回填”减去一的次数。

注:本题 data 目录的数据有可能是使用 data.py 和 gen.* 生成的,属于自造数据或者网络重建数据。