贪心算法:使用出现次数桶和三个单调下降指针,每次取剩余数量最多的三种半径各减一,直到无法再取齐三种半径为止。
OJ: roj
题目 ID: 5010
难度:提高+/省选-
标签:贪心三指针桶排序
创建: 2024-10-18 10:00
更新: 2024-10-18 10:00
形式化题目
给定
正解
思路
这道题可以使用贪心的思想:为了尽可能多地组合出三层蛋糕,我们每次组装时,应该优先选择剩余数量最多的那些半径的蛋糕。
如果我们总是从剩余数量前三大(不同半径种类)的蛋糕中各取一个来组成三层蛋糕,是否一定最优呢?可以通过交换论证证明:总是取数量最多的不仅能够避免“数量多但半径不匹配”导致最终剩下大量同一种类的蛋糕,并且等价于在保证合法性前提下的最优化策略(类似 Hall 定理推导出的结论)。
为了快速进行“取剩余数量最大的三种半径”,我们可以进行如下优化:
- 统计出现次数:使用
cnt[r]记录半径为r的蛋糕有多少个。 - 频率桶排序(桶的桶):使用
bucket[k]记录“出现次数恰好为k的蛋糕半径”有几种。 - 三指针下降:使用三个指针
在 bucket数组上从大到小扫描。因为在不断取蛋糕的过程中,某一种半径剩余的个数只会减少(比如从变到 ),所以指针总体上只会递减。 每一轮:
- 指针
找到一个 bucket[x] > 0,拿走一种半径的一个蛋糕,bucket[x]--; - 指针
找到一个 bucket[y] > 0,拿走另一种半径的一个蛋糕,bucket[y]--; - 指针
找到一个 bucket[z] > 0,拿走第三种半径的一个蛋糕,bucket[z]--。 - 然后分别将拿走的这三种半径的剩余数量(即
)放回到对应的桶中(如果大于 的话)。
直到某一次取数时,至少有一个指针找不到大于
代码
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;
}复杂度
- 时间复杂度:读入需要
。指针 是单调不增的,最大值是最高频次( ),即便在每一轮中回填较小的频次,但因为每一轮都消耗 个蛋糕并且每次扫描非空桶,总体指针移动和桶的增减操作时间均摊也是 级别的。总时间复杂度 。 - 空间复杂度:需要
cnt和bucket两个大小约为的数组。题目数据范围 ,数组消耗极少内存。空间复杂度为 。
总结
本题通过“每次贪心选择剩余数量最多的三个不同元素”可以得到最优解。利用“频次桶+下降指针”的技巧可以将这个选择过程优化至
注:本题
data目录的数据有可能是使用data.py和gen.*生成的,属于自造数据或者网络重建数据。