传智杯 第六届-复赛-C

题目描述:

        小红有一个数组,她每次可以选择数组的一个元素 xxx ,将这个元素分成两个元素 aaa 和 bbb ,使得 a+b=xa+b=xa+b=x。请问小红最少需要操作多少次才可以使得数组的所有元素都相等。

输入描述:

        第一行输入一个整数 n(1≤n≤10^5) 表示数组长度。第二行输入 n个整数表示数组 a(1≤ai≤10^9) 。

输出描述:

        输出一个整数表示答案。

示例1

输入:

2
2 4

输出:

1

说明:

操作1次,将4分成2和2,数组变成[2,2,2]。

解题步骤1(错误):

        由题可知,想要将所有的正整数都转换成一个数,那么找到这些整数的最大公因子即可。

        ①输入

        ②将各个整数所有小于最小正整数的因子所对应的数组进行++:先创建一个数组用于存储该下标i可以是多少个正整数的因子,其中该数组的个数应该为最小整数+1个;再利用双层循环来判断该数组下标i是否可以成为因子,如果可以则其值+1,最终就可以填充b数组b中的值

        ③找到最大共同的因子:即数组b中的数组下标j对应的值为n,这个最大的公共因子就是j

        ④计算次数:每个数进行转换的时候,需要转换  /公共因子-1 次

        ⑤输出

代码:

#include<iostream>
#define MAX 1000000000
using namespace std;
int  main()
{//输入int n;  //整数个数cin >> n;int* a = new int[n];    //存储整数int mi = MAX;    //记录最小的正整数for (int i = 0;i < n;i++){cin >> a[i];mi = min(a[i], mi);}//将各个整数所有小于最小正整数的因子所对应的数组进行++int* b = new int[mi + 1];   //存储因子是多少个正整数的因子for (int i = 0;i < mi + 1;i++)   //初始化b{b[i] = 0;}for (int i = 0;i < n;i++){for (int j = 1;j < mi + 1;j++){if (a[i] % j == 0)  //可以被整除,即j是因子{b[j]++;}}}//找到最大共同的因子(即其数组对应的值为n)int x = 0;   //最终数组变成的元素for (int j = mi;j > -1;j--){if (b[j] == n){x = j;break;}}//计算次数int count = 0;   //操作次数for (int i = 0;i < n;i++){count += a[i] / x - 1;}//输出cout << count << endl;system("pause");return 0;
}

错误原因:

        在步骤②时,如果最小的整数过大,将会导致计算b的次数过大;当整数的个数过大的时候,也将会导致计算b的次数过大,所以最终就会导致运算超时

解题思路2(改进):

        在计算b的时候,可以利用gcd()函数来计算出最大的公约数,直接过渡到计算操作次数就可以了。

注意:

        ①操作次数可能会很大,必须使用long long的数据类型。

代码 :

#include<iostream>
using namespace std;//找最大公约数
int gcd(int a, int b)
{while (b != 0){int temp = b;b = a % b;a = temp;}return a;
}int  main()
{//输入int n;  //整数个数cin >> n;int* a = new int[n];    //存储整数cin >> a[0];int g = a[0];   //最大公约数for (int i = 1;i < n;i++){cin >> a[i];g = gcd(g, a[i]);}//计算次数long long count = 0;   //操作次数for (int i = 0;i < n;i++){count += a[i] / g - 1;}//输出cout << count << endl;system("pause");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/460889.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

华为配置 之 GVRP协议

目录 简介&#xff1a; 配置GVRP&#xff1a; 总结&#xff1a; 简介&#xff1a; GVRP&#xff08;GARP VLAN Registration Protocol&#xff09;&#xff0c;称为VLAN注册协议&#xff0c;是用来维护交换机中的VLAN动态注册信息&#xff0c;并传播该信息到其他交换机中&…

外包干了7天,技术明显退步。。。。。

先说一下自己的情况&#xff0c;本科生&#xff0c;22年通过校招进入南京某软件公司&#xff0c;干了接近2年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了2年的功能测试&…

openGauss开源数据库实战十

文章目录 任务十 openGauss逻辑结构:数据库管理任务目标实施步骤一、登录到openGauss二、创建数据库三、查看数据库集群中有哪些数据库四、查看数据库默认表空间的信息五、查看数据库下有哪些模式六、查看数据库下有哪些表七、修改数据库的默认表空间八、重命名数据库九、删除数…

H3C OSPF配置

OSPF配置实验 实验拓扑图 实验需求 1.配置IP地址 2.分区域配置OSPF&#xff0c;实现全网互通 3.为了路由结构稳定&#xff0c;要求路由器使用环回口作为Router-id&#xff0c;ABR的环回口宣告进骨干区域 实验配置 1.配置IP地址 R1&#xff1a; <H3C>system-view …

飞桨首创 FlashMask :加速大模型灵活注意力掩码计算,长序列训练的利器

在 Transformer 类大模型训练任务中&#xff0c;注意力掩码&#xff08;Attention Mask&#xff09;一方面带来了大量的冗余计算&#xff0c;另一方面因其 O ( N 2 ) O(N^2) O(N2)巨大的存储占用导致难以实现长序列场景的高效训练&#xff08;其中 N N N为序列长度&#xff09;…

乘云而上,OceanBase再越山峰

一座山峰都是一个挑战&#xff0c;每一次攀登都是一次超越。 商业数据库时代&#xff0c;面对国外数据库巨头这座大山&#xff0c;实现市场突破一直都是中国数据库产业多年夙愿&#xff0c;而OceanBase在金融核心系统等领域的攻坚克难&#xff0c;为产业突破交出一副令人信服的…

为什么要使用Golang以及如何入门

什么是golang&#xff1f; Go是一种开放源代码的编程语言&#xff0c;于2009年首次发布&#xff0c;由Google的Rob Pike&#xff0c;Robert Griesemer和Ken Thompson开发。基于C的语法&#xff0c;它进行了一些更改和改进&#xff0c;以安全地管理内存使用&#xff0c;管理对象…

《文心一言插件设计与开发》赛题三等奖方案 | NoteTable

一年一度的 CCF大数据与计算智能大赛&#xff08;简称2024 CCF BDCI大赛&#xff09;又开始啦~~ 程序员们可冲一波嗷~ 大赛地址&#xff1a;http://go.datafountain.cn/6506 现在我们再次释放往届获奖方案&#xff0c; 为新一届大赛的同学们提供一些方案和灵感参考~ 大家借鉴借…

el-dialog支持全局拖拽功能

1.首先在全局的组件实现拖拽功能&#xff0c;结构如下 dialogDrag.vue的内容 <script>export default {mounted() {// 获取当前的dialog及其headerlet aimDialog this.$el.getElementsByClassName(el-dialog)[0];let aimHeader this.$el.getElementsByClassName(el-d…

XCode16中c++头文件找不到解决办法

XCode16中新建Framework&#xff0c;写完自己的c代码后&#xff0c;提示“<string> file not found”等诸如此类找不到c头文件的错误。 工程结构如下&#xff1a; App是测试应用&#xff0c;BoostMath是Framework。基本结构可以参考官方demo&#xff1a;Mix Swift and …

开源代码管理平台Gitlab如何本地化部署并实现公网环境远程访问私有仓库

文章目录 前言1. 下载Gitlab2. 安装Gitlab3. 启动Gitlab4. 安装cpolar5. 创建隧道配置访问地址6. 固定GitLab访问地址6.1 保留二级子域名6.2 配置二级子域名 7. 测试访问二级子域名 前言 本文主要介绍如何在Linux CentOS8 中搭建GitLab私有仓库并且结合内网穿透工具实现在公网…

JavaEE初阶---网络原理(四)--IP协议/DNS协议

文章目录 1.初识网络层&#xff08;了解即可&#xff09;2.地址管理2.1动态分配2.2网络地址转换2.3IP-v6最终解 3.网段划分4.以太网协议--数据链路层5.DNS应用层协议 1.初识网络层&#xff08;了解即可&#xff09; 网络层做的事情就是下面的两个&#xff1a; 1&#xff09;地…

4.2-6 使用Hadoop WebUI

文章目录 1. 查看HDFS集群状态1.1 端口号说明1.2 用主机名访问1.3 主节点状态1.4 用IP地址访问1.5 查看数据节点 2. 操作HDFS文件系统2.1 查看HDFS文件系统2.2 在HDFS上创建目录2.3 上传文件到HDFS2.4 删除HDFS文件和目录 3. 查看YARN集群状态4. 实战总结 1. 查看HDFS集群状态 …

EMS专题 | 5个必须知道的温度监测系统入门知识

在保护温度敏感资产方面&#xff0c;可靠的温度监测技术扮演着至关重要的角色。为了帮助您深入了解这一关键技术&#xff0c;我们特别推出了EMS&#xff08;环境监测系统&#xff09;专题文章系列。内容将由浅入深&#xff0c;从基础原理到实际应用&#xff0c;从行业标准到解决…

代码随想录-字符串-反转字符串中的单词

题目 题解 法一:纯粹为了做出本题&#xff0c;暴力解 没有技巧全是感情 class Solution {public String reverseWords(String s) {//首先去除首尾空格s s.trim();String[] strs s.split("\\s");StringBuilder sb new StringBuilder();//定义一个公共的字符反转…

关于Android Studio Koala Feature Drop | 2024.1.2下载不了插件的解决办法

解决 androidStudio Settings->Plugins下载插件&#xff0c;点击install后没反应&#xff0c;同时插件描述相关显示不出来 第一步&#xff1a; 第二步&#xff1a; 点击设置&#xff0c;勾选Auto-detect proxy settings&#xff0c;输入网址 https://plugins.jetbrains.com…

[论文阅读] Improved Baselines with Visual Instruction Tuning

启发&#xff1a; 1、LLaVA-1.5和LLaVA以及其他大模型相比&#xff0c;做出了哪些改进&#xff1f; &#xff08;1&#xff09;使用CLIP-ViT-L-336px作为视觉编码器&#xff0c;使模型能处理336px的高分辨率图像&#xff0c;这使得模型能从图像中提取出更多细节信息。此外&am…

大语言模型(LLM)快速理解

自2022年&#xff0c;ChatGPT发布之后&#xff0c;大语言模型&#xff08;Large Language Model&#xff09;&#xff0c;简称LLM掀起了一波狂潮。作为学习理解LLM的开始&#xff0c;先来整体理解一下大语言模型。 一、发展历史 大语言模型的发展历史可以追溯到早期的语言模型…

「C/C++」C++标准库之#include<fstream>文件流

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…

十六:Python学习笔记-- 爬虫(2)requests 模块详解

目录 安装 requests 模块 基本请求方法 GET 请求 POST 请求 PUT 请求 DELETE 请求 添加请求头&#xff1a; 处理查询参数&#xff1a; 文件上传&#xff1a; 常见响应状态码 访问超时 cookie的查询和设置 查询 Cookies 设置 Cookies 设置爬虫代理 小试牛刀 安装 …