当前位置:首页 » 《随便一记》 » 正文

石子游戏(后缀和)_irrationality的博客

20 人参与  2022年02月26日 15:41  分类 : 《随便一记》  评论

点击全文阅读


有 n 堆石子,石子数量分别为 a1,a2,…,an。

现在,需要你通过取石子操作,使得所有堆石子的数量都相同。

一轮取石子操作的具体流程为:

  1. 设定一个石子数量上限 h
  2. 检查每堆石子,对于石子数量大于 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 <stdio.h>
#include <string.h>
#include <iostream>
#include <cstring>
#include <algorithm>

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]个,

以此类推。

最后如果手上还有石子,利用!!判断,直接加上即可。

 


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/35420.html

石子  高度  数量  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • (番外)+(全书)霍沉洲沈青禾此去经年人未还(霍沉洲沈青禾)_(霍沉洲沈青禾此去经年人未还)列表_笔趣阁(霍沉洲沈青禾)
  • (番外)+(全书)霍沉洲沈青禾(此去经年人未还霍沉洲沈青禾)完结_(霍沉洲沈青禾)列表_笔趣阁(此去经年人未还霍沉洲沈青禾)
  • 「重回八零,拒绝替嫁冲喜」章节彩蛋限时释出‌_卫东玉兰苏夏人气小说未删减节选
  • 重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费
  • 傅雅宁的神女老婆,却在背地承欢作乐顾尘傅雅宁全书在线
  • 全文神女老婆,却在背地承欢作乐全局(顾尘傅雅宁)列表_全文神女老婆,却在背地承欢作乐全局
  • (番外)+(全书)此去经年人未还全书+番外+后续免费下载_(沈青禾霍沉洲)此去经年人未还全书+番外+后续列表_笔趣阁(沈青禾霍沉洲)
  • 完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续列表_完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续(林梦婉)
  • 妻子辱我爸受贿自杀,我掏出一等军功章节选推荐_[陈素云辰朋友]小说精彩章节分享
  • 全书浏览苔藓爬满旧日诺言新上(顾砚廷慕晚夏)_苔藓爬满旧日诺言新上(顾砚廷慕晚夏)全书结局
  • 顾尘傅雅宁(神女老婆,却在背地承欢作乐+后续+结局)结局_(顾尘傅雅宁神女老婆,却在背地承欢作乐+后续+结局全书结局)结局列表_笔趣阁(顾尘傅雅宁)
  • 「老婆怀上助理的孩子后,助理要求我净身出户」章节限时抢先看‌_「黄秋雅秋雅姐刘嘉铭」后续完结版

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1