c语言|石子游戏(后缀和)
有 n 堆石子,石子数量分别为 a1,a2,…,an。
现在,需要你通过取石子操作,使得所有堆石子的数量都相同。
一轮取石子操作的具体流程为:
- 设定一个石子数量上限 h
- 检查每堆石子,对于石子数量大于 h的石子堆,取出多余石子,使其石子数量等于 h
- 要求,在一轮取石子操作中取走的石子数量不得超过 k
- 请计算并输出为了使得所有堆石子的数量都相同,最少需要进行多少轮取石子操作。
- 输入格式
第一行包含两个整数 n,k。
第二行包含 n个整数 a1,a2,…,an。
输出格式
一个整数,表示所需的最少取石子操作轮次。
数据范围
前六个测试点满足, 1≤n≤k≤10。
所有测试点满足,1≤n≤2×10^5,n≤k≤10^9,1≤ai≤2×10^5。 输入样例1:
5 5 3 1 2 2 4
输出样例1:
2
输入样例2:
4 5 2 3 4 5
输出样例2:
2
#include
#include
#include
#include
#include using namespace std;
typedef long long LL;
int a[200005], n, m;
LL c[200005];
int main() {
scanf("%d%d", &n, &m);
int mins = 2e5;
for (int i = 1;
i <= n;
++i) {
scanf("%d", a + i);
++c[a[i]];
//桶装法 看个数
if (a[i] < mins) mins = a[i];
//最小值,进行轮数最少,那么就要把所有都变成堆堆中的最小即可
}
int res = 0;
LL cur = 0;
for (int i = 2e5;
i > mins;
--i) {
c[i] += c[i + 1];
//后缀和 表示由后往前一共有多少《堆》石子,模拟从高度h到高度h-1取石子,因为高度为h-1的石子包含了最高层为h-1的石子,以及比h更高的石子
if ((cur += c[i]) > m) {//大于了一轮的数目,那么最后就要下一轮
++res, cur = c[i];
}
}
printf("%d\n", res + !!cur);
//!! 把非0转化为1 把0转化成0
return 0;
}
这个题巧妙地用到了后缀和,同时向我们展示了石子堆砌的魅力。
首先看每个高度有多少石子,其次看高度的最小值。
要把所有的石子变到这个高度。
那么,高度为h 就有c[h]个,
高度为h-1就有c[h-1]个,
以此类推。
最后如果手上还有石子,利用!!判断,直接加上即可。
文章图片
【c语言|石子游戏(后缀和)】
推荐阅读
- 游戏IP(立足于玩家情感的粉丝经济)
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 一起来学习C语言的字符串转换函数
- C语言字符函数中的isalnum()和iscntrl()你都知道吗
- C语言浮点函数中的modf和fmod详解
- C语言中的时间函数clock()和time()你都了解吗
- 人生游戏--是游戏,还是人生()
- 「按键精灵安卓版」关于全分辨率脚本的一些理解(非游戏app)
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- (小说)月流水几亿的火爆游戏养成记