首页 > 试题广场 >

分石子

[编程题]分石子
  • 热度指数：1370 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛有n堆石子堆，第i堆一共有a_i个石子。

牛牛可以对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。

现在牛牛需要通过分裂得到m堆石子，他想知道这m堆石子的最小值最大可以是多少？
示例1

输入

3,5,[3,5,6]

输出

2

说明

把5分裂成2和3
把6分裂成2和4
得到五堆石子[3,2,3,2,4]

备注:


第一个参数n代表石子堆的个数
第二个参数m表示需要得到的石子堆数。
第三个参数vector a代表每堆石子堆的石子个数
算法知识视频讲解
开通博客
头像 你好！我是小明同学。
发表于 2021-01-30 20:05:33
分石子问题 题解源自：牛客大佬——745599318 思路：#令res表示分裂后m堆的最小值，#res一定在[1, min{a[i], i=0,1...,n-1}]区间内，记左右区间分别为left, right。#mid初始值去区间中值，即mid=left+(right-left)/2，利用二分 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-14 15:14:03
思路： 题目的主要信息： 现有n堆石子，每堆数量记录在数组a 可以对任意石子数大于1的堆分裂成两堆数量大于等于1的石子 现需要分裂成m堆石子()，问这m堆石子最小值最大可以是多少？ 方法一：暴力法具体做法：我们都知道分裂只会让石子更少，因此最小值一定小于等于分裂前数组最开始的最小值。因此我们从数 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 未来0116
发表于 2021-08-15 21:23:02
一.题目描述NC565分石子有n堆石子堆，第i堆一共有ai个石子。对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。现在需要通过分裂得到m堆石子，求这m堆石子的最小值最大可以是多少？二.算法(暴力)可以采用暴力模拟的方法来解决，由于将石子不断进行分裂操作所以最 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 changed.
发表于 2021-10-12 17:09:37
题意整理： 题目以数组a给出n个正整数，可以对一个整数进行操作使其拆分为两个正整数，拆分得到的两个正整数之和为原本的正整数，求得使分隔完成后存在m个正整数时，这些正整数中的最小值的最大可以取得多少。其中n≤m≤∑an\leq m \leq \sum a n≤m≤∑a 由于m比所有数字总和小，所以保证 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Peterliang
发表于 2021-10-12 13:54:23
NC565 题解 | #分石子# 题意分析 给出n堆石头以及每堆石头的数量，然后我们可以将任意堆石头数量大于1的分为两堆，问最后分为m堆中，分得的所有堆里面的最小值最大是多少？ 思路分析 对于这种最小值最大，最大值最小等的问题，一半都是采用的是二分的方法进行处理。我们先判断怎样二分具有单调性 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ivy2019
发表于 2022-09-11 18:33:52
求最小值的最大可能，使用二分法。 确定思路后最重要的是找到left，right分别是什么。 本题中因为题面明确说“分裂成两堆新的石子数量都大于等于1的石子堆”，故left初始值为1； 另，因为本题死分石子，故最小值的最大值为初始数组中的最小值，再分下去只能小于等于初始数组中的最小值 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-10-02 17:41:09
题目： 有n堆石子堆，第i堆一共有a[i]个石子。 可以对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。需要通过分裂得到m堆石子，他想知道这m堆石子的最小值最大可以是多少？ 方法一：暴力查找 要查找的最大的最小值在[1,min(a[i])][1,min(a[ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分
难度：
2条回答 5339浏览

热门推荐

通过挑战的用户

查看代码

相关试题

分石子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号