上课睡觉(2023寒假每日一题 4)
有 NNN 堆石子,每堆的石子数量分别为 a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。
你可以对石子堆进行合并操作,将两个相邻的石子堆合并为一个石子堆,例如,如果 a=[1,2,3,4,5]a=[1,2,3,4,5]a=[1,2,3,4,5],合并第 2,32,32,3 堆石子,则石子堆集合变为 a=[1,5,4,5]a=[1,5,4,5]a=[1,5,4,5]。
我们希望通过尽可能少的操作,使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。
本题一定有解,因为可以将所有石子堆合并为一堆。
输入格式
第一行包含整数 TTT,表示共有 TTT 组测试数据。
每组数据第一行包含整数 NNN。
第二行包含 NNN 个整数 a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。
输出格式
每组数据输出一行结果。
数据范围
1≤T≤10,1≤T≤10,1≤T≤10,
1≤N≤105,1≤N≤10^5,1≤N≤105,
0≤ai≤106,0≤a_i≤10^6,0≤ai≤106,
∑i=1nai≤106,∑_{i=1}^na_i≤10^6,∑i=1nai≤106,
每个输入所有 NNN 之和不超过 10510^5105。
输入样例:
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
输出样例:
3
2
0
样例解释
第一组数据,只需要用 333 个操作来完成:
1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
第二组数据,只需要用 222 个操作来完成:
2 2 3
-> 2 5
-> 7
第三组数据,我们什么都不需要做。
#include<iostream>using namespace std;const int N = 100010;typedef long long LL;int n;
int a[N];bool check(LL x){LL sum = 0;for(int i = 0; i < n; i++){sum += a[i];if(sum == x) sum = 0;else if(sum > x) return false;}return true;
}int main(){int t;scanf("%d", &t);while(t--){scanf("%d", &n);LL sum = 0;for(int i = 0; i < n; i++) scanf("%d", &a[i]), sum += a[i];for(int i = n; ; i--){if(sum % i == 0 && check(sum / i)){printf("%d\n", n - i);break;}}}return 0;
}
相关文章:
上课睡觉(2023寒假每日一题 4)
有 NNN 堆石子,每堆的石子数量分别为 a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。 你可以对石子堆进行合并操作,将两个相邻的石子堆合并为一个石子堆,例如,如果 a[1,2,3,4,5]a[1,2,3,4,5]a[1,2,3,4,5],合并第 2,32…...

【Selenium学习】Selenium 中常用的基本方法
1.send_keys 方法模拟键盘键入此方法类似于模拟键盘键入。以在百度首页搜索框输入“Selenium”为例,代码如下:# _*_ coding:utf-8 _*_ """ name:zhangxingzai date:2023/2/13 form:《Selenium 3Python 3自动化测试项目实战》 …...

python练习——简化路径
项目场景: 给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 /开头),请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中,一个点(.)表示当前目录本…...
2023新华为OD机试题 - 火星文计算2(JavaScript) | 刷完必过
火星文计算 2 题目 已知火星人使用的运算符号为#;$ 其与地球人的等价公式如下 x#y=4*x+3*y+2 x$y=2*x+y+3 x y是无符号整数 地球人公式按照 c 语言规则进行计算 火星人公式中#符优先级高于$ 相同的运算符按从左到右的顺序运算 输入 火星人字符串表达式结尾不带回车换行 输入…...

前端插件重磅来袭
“你值得拥有”专栏系列上新啦,今日推出“手写前端插件”项目,作为一个前端中高级工程师,手写前端树形菜单插件、弹出层插件、日历插件、分页插件、选项卡插件、进度条插件等是必备的技能,让你的前端技术百尺竿头更进一步…...

深入工厂|高精密多层板是如何被智造出来的?
或许有很多人从网络上见过各种教程,告诉你单层板是什么,多层板是什么,他们该如何做出来,但是在具体制造时却全凭想象,今天,就让我们来实地看看,精密的多层板是如何被制造出来的!今天…...
代理模式动态代理
什么是代理模式? 代理模式是开发中常见的一种设计模式,使用代理模式可以很好的对程序进行横向扩展。代理,顾名思义就是一个真实对象会存在一个代理对象,并且代理对象可以替真实对象完成相应操作,外部通过代理对象来访…...
Mysql之二进制日志
目录 二进制日志 12-37 二进制日志格式 基于行的二进制日志 基于语句的二进制日志 混合格式二进制日志 复制日志 12-42 故障安全 (Crash-Safe) 复制 多源复制 二进制日志 12-37 二进制日志: • 包含数据和模式更改及其时间戳 – 基于语句 或 基于行 的日志…...

kail工具的使用--- cewl
1.介绍 Cewl是一款采用Ruby开发的应用程序,可以给他的爬虫指定URL地址和爬取深度,还可以添加外部链接,接下来Cewl会给你返回一个字典文件,你可以把字典用到类似John the Ripper这样的密码破解工具中。 2.使用 输入以下命令之后…...
【蓝桥杯集训1】前缀和专题(2 / 5)
目录 前缀和模板 !3956. 截断数组 - 前缀和枚举 前缀和模板 活动 - AcWing import java.util.*;class Main {static int N100010;static int[] anew int[N],snew int[N];public static void main(String[] args){Scanner scnew Scanner(System.in);int nsc.nex…...

基于模块联邦的微前端实现方案
一、 微前端应用案例概述 当前案例中包含三个微应用,分别为 Marketing、Authentication 和 Dashboard Marketing:营销微应用,包含首页组件和价格组件 Authentication:身份验证微应用,包含登录组件 Dashboard&#x…...

【单目标优化算法】食肉植物优化算法(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
ANTLR4入门学习(四)
ANTLR4入门学习(四)一、设计语法1.语法2.ANTLR核心标记3.常见计算机语言模式4.左右递归5.识别常见的语法结构5.1 匹配标识符5.2 匹配数字5.3 匹配字符串常量5.4 匹配注释和空白字符5.5 基础的语法规则5.6 划定词法分析器和语法分析器的界线一、设计语法 …...
Android okhttp3中发送websocket消息,并通过mockwebserver将一个安卓设备模拟成服务器接发消息
websocket 提供了客户端和服务端的长链接,允许客户端和服务端双向发送消息 okhttp 提供了使用websocket 相关接口议。同时为方便单元测试,又提供了mockwebserver可以把一个安卓客户端作为服务端接受消息。 websocket使用 权限 <uses-permission an…...

MySQL系统变量和自定义变量
1 系统变量1.1 查看系统变量可以使用以下命令查看 MySQL 中所有的全局变量信息。SHOW GLOBAL VARIABLES; MySQL 中的系统变量以两个“”开头。global 仅仅用于标记全局变量;session 仅仅用于标记会话变量;首先标记会话变量,如果会话变量不存在…...

基于Python来爬取某音动态壁纸,桌面更香了!
至于小伙伴们想要这个封图,我也没有。不过继续带来一波靓丽壁纸,而且是动态的,我的桌面壁纸又换了:每天换着花样欣赏一波波动态壁纸桌面立刻拥有了高颜值,简直跟刷美女短视频一样啊。对的,这些动态壁纸就是…...

[数据库]表的约束
●🧑个人主页:你帅你先说. ●📃欢迎点赞👍关注💡收藏💖 ●📖既选择了远方,便只顾风雨兼程。 ●🤟欢迎大家有问题随时私信我! ●🧐版权:本文由[你帅…...

VisualGDB 5.6R9 FOR WINDOWS
Go cross-platform with comfort VisualGDB 是 Visual Studio 的一个非常强大的扩展,它允许您调试或调试嵌入式系统。这个程序有一个非常有吸引力的用户界面,它有许多调试或调试代码的功能。VisualGDB 还有一个向导可以帮助您调试程序,为您提…...
Yolov8的多目标跟踪实现
Yolov8_tracking 2023年2月,Yolov5发展到yolov8,这世界变得真快哦。Yolov8由ultralytics公司发布,yolov6-美团,yolov7-Alexey Bochkovskiy和Chien-Yao Wang,其各有高招,对yolov5均有提升。mikel-brostrom在…...

28--Django-后端开发-drf之自定义全局异常、接口文档生成以及三大认证源码分析
一、django请求的整个生命周期 旅程: drf处于的位置:路由匹配成功,进视图类之前 1、包装了新的request 2、处理了编码(urlencoded,formdata,json) 3、三大认证 4、进了视图类(GenericAPIView+ListModelMixin) 进行了过滤和排序去模型中取数据分页序列化返回5、处理了…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...