[Daimayuan] 一半相等(C++,数学)

news/2024/4/15 8:19:28

给定 n n n n n n 为偶数)个整数数组 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an

考虑这样的一个 k k k,每次操作选定一个 i i i,将 a i a_i ai 减少 k k k,执行多次(可能 0 0 0 次)后使得数组中至少有一半的元素相等,求最大的 k k k,如果这样的 k k k 为无穷大,输出 − 1 −1 1

输入格式

输入包含两行,第一行为一个正整数 n n n,表示数组大小。第二行为 n n n 个整数 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an

输出格式

输出题意中的 k k k

样例输入

8
-1 0 1 -1 0 1 -1 0

样例输出

2

数据规模

4 ≤ n ≤ 100 4≤n≤100 4n100,数据保证 n n n 为偶数

− 1 0 6 ≤ a i ≤ 1 0 6 −10^6≤a_i≤10^6 106ai106

解题思路

既然有一半的元素能够在相同的 k k k的作用下达到相等即达到一个共同的值。

那么这一半的元素到这个共同值的距离可以被 k k k整除,而要求 k k k尽可能的大,故类似于最大公约数。

(当数组中已经有就有一半的元素相等,那么可以直接输出 − 1 -1 1。)

但是我们要求哪一半元素?又是要求到谁的距离呢?

(注意是距离,也就是差值的绝对值,因为转化是双向的,如 1 − 2 = − 1 , − 1 − ( − 2 ) = 1 1-2=-1,-1-(-2)=1 12=1,1(2)=1

因为存在这样一种情形:一半的元素到 x x x的距离的gcd,大于到 y y y的距离的gcd

例如: 2 , 5 2,5 2,5 0 0 0的距离的最大公约数是 1 1 1,而到 − 1 -1 1的距离的最大公约数是 3 3 3

所以选择的目标位置会对最终的结果产生影响。

但是我们可以证明目标位置一定在给定的数组中:

直观起见,以下面这个数组为例,应该选择的一半元素是 2 , 5 , 8 , 8 2,5,8,8 2,5,8,8

2 5 3 3 8 8

对此,我们可以选择 − 1 -1 1作为目标位置,拿到最大公约数 3 3 3

但是我们同样也可以选择 2 2 2作为目标位置,拿到最大公约数 3 3 3

我们想不出一种比较好的算法来解决以上的两个问题,所以采用暴力搜索(毕竟 n ≤ 100 n\le100 n100):

1)尝试将每一个数作为目标位置;

2)计算其他所有数到目标位置的距离;

3)求出距离的所有的因子并统计其出现的频率;

4)保留最大的因子。

最后,AC代码如下:

#include <iostream>
#include <cmath>
#include <map>
using namespace std;
const int max_n = 100;int arr[max_n];
map<int, int>freqs;void division(int x) {int i;for (i = 1; i * i < x; i++) {if (x % i == 0) {freqs[i]++;freqs[x / i]++;}}if (i * i == x) freqs[i]++;
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {cin >> arr[i];}int ans = 0;for (int i = 0; i < n; i++) {const int temp = arr[i];int cnt = 0;for (int j = 0; j < n; j++) {if (temp == arr[j]) cnt++;else division(abs(temp - arr[j]));}if (cnt >= n / 2) {cout << -1 << endl;return 0;}for (auto iter : freqs)if (iter.second + cnt >= n / 2) ans = max(ans, iter.first);freqs.clear();}cout << ans << endl;return 0;
}

http://www.ppmy.cn/news/399004.html

相关文章

动态规划经典题型:最小路径和、所有路径

题目1&#xff1a;最小路径和 给定一个包含非负整数的 *m* x *n* 网格 grid &#xff0c;请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 说明&#xff1a;每次只能向下或者向右移动一步。 示例&#xff1a; 输入&#xff1a;grid [[1,3,1],[1…

DeepSpeed零冗余优化器Zero Redundancy Optimizer

零冗余优化器 内容 零概述培训环境启用零优化 训练 1.5B 参数 GPT-2 模型训练 10B 参数 GPT-2 模型使用 ZeRO-Infinity 训练万亿级模型 使用 ZeRO-Infinity 卸载到 CPU 和 NVMe分配 Massive Megatron-LM 模型以内存为中心的平铺注册外部参数提取权重 如果您还没有这样做&…

常见笔记本BIOS启动键总结( 超级详细 ! ! ! )

最近都在和笔记本打交道&#xff0c;自己拿公司电脑当小白鼠&#xff0c;对不同品牌进行装机。我将我了解到的笔记本电脑启动键列举一下&#xff0c;仅供大家参考&#xff1a; 1.苹果笔记本: (启动option键) 雷神笔记本: F2 2常见笔记本 3. 常见台式机 4. 常见组装机 注意:上…

计算机软硬件维修的书籍,电脑软硬件维修宝典 PDF 超清版

一般来说&#xff0c;计算机故障主要有软件故障、硬件故障、网络故障、网络故障等三种可能性。软硬件故障几乎包含了计算机的所有故障种类&#xff0c;本书总结了计算机软硬件故障诊断修复方法和大量经典案例分析&#xff0c;让读者掌握了计算机故障的修复方法。本书分成四大篇…

[计算机故障]toshiba笔记本计算机无法正常启动,每次均需要按ESC

同事一台toshiba的笔记本计算机,无法正常启动,每次均需要按ESC才可以正常后续动作。 之后系统可以正常工作。 排查过程&#xff1a; 1、尝试恢复bios到默认配置&#xff1b;不行&#xff0c;而且不小心搞了个蓝屏&#xff0c;还好记得是“SATA controller mode”设置的问题&am…

Verilog 高级知识点---状态机

目录 状态机 1、Mealy 状态机 2、Moore 状态机 3、三段式状态机 状态机 Verilog 是硬件描述语言&#xff0c;硬件电路是并行执行的&#xff0c;当需要按照流程或者步骤来完成某个功能时&#xff0c;代码中通常会使用很多个 if 嵌套语句来实现&#xff0c;这样就增加了代码…

硬件大熊原创合集(2023/03更新)

3月份更新篇章&#xff1a; 《智能家居行业研究与场景分析》 中国全屋智能行业产业链总览图 为什么有些SRRC型号核准代码要加“M” 和菜头在聊ChatGPT时写过一句话&#xff1a;"大家更愿意通过效果去理解和认识一件事&#xff0c;不大喜欢通过原理和机制去理解一件事"…

技能Get·手动更新HP笔记本BIOS过程记录

阅文时长| 0.17分钟字数统计| 279.2字符主要内容| 1、引言&背景 2、详细步骤 3、声明与参考资料 『技能Get手动更新HP笔记本BIOS过程记录』编写人| SCscHero 编写时间| 2021/7/30 PM12:18文章类型| 系列完成度| 已完成座右铭每一个伟大的事业&#xff0c;都有一个微不足道的…

计算机维护需要那些工具,电脑从菜鸟到扫盲第一篇之维修工具选择

前言&#xff1b;这些年大家基本上稍微有点动手能力的会自己DIY动手组装电脑&#xff0c;一方面是可以以更低价格淘到更具性价比的配件&#xff0c;另一方面也体会装机的乐趣&#xff0c;那么在装机前我们就必须对硬件有所了解&#xff0c;为此我专门整理了先关硬件资料以便于用…

Java面试宝典(超级详细)

一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java Development Kit 的简称,java 开发工具包,提供了 java 的开发环境和运行环境。JRE:Java Runtime Environment 的简称,java 运行环境,为 java 的运行提供了所需环境。具体来说 JDK 其实包含了 JRE,同时还包含了编译 …

OpenGL 超级宝典笔记 —— 位图

位图 最初的电子计算机&#xff0c;只能显示单色&#xff08;绿色或琥珀色&#xff09;图形&#xff0c;每一个像素只有两种状态打开和关闭。在计算器图形学前期&#xff0c;图像数据是用位图来表示的&#xff0c;位图就是一系列的 0 和 1&#xff0c;表示打开或关闭的像素值。…

OpenGL 超级宝典笔记 —— 雾

应用雾 雾是 OpenGL 支持的一种易于使用的特殊效果。在使用雾时&#xff0c;OpenGL 把雾的颜色与完成所有其他颜色计算的几何图元进行混合。雾与几何图元的混合程度取决于几何图元离观察者的距离。雾可以使物体逐渐模糊最终消失在雾色里&#xff08;就像在雾中远去的父亲的背影…

OpenGL 超级宝典笔记 —— 混合

混合 在正常情况下&#xff0c;OpenGL 渲染时会把颜色值输入到颜色缓冲区中&#xff0c;深度值输入到深度缓冲区中。如果我们关闭深度测试&#xff0c;那么新的颜色值会简单地覆盖已经存在于颜色缓冲区中的值。当开启深度测试时&#xff0c;颜色段只有在通过深度测试时&#x…

功夫不负有心人,机械师T58完美吃上黑贫果

说在前面 一直以来梦想着能拥有一台Mac&#xff0c;奈何那遥不可及的价格&#xff0c;让本喵的只能望果兴叹。其实本喵更痴迷的不是它的外观和做工&#xff0c;而是那优雅的操作系统。既然钱包不允许&#xff0c;就只能找个本子装个黑果体验一把咯。 这里郑重声明&#xff1a;…

玄派玄智星01笔记本电脑系统故障无法开机怎么办?

玄派玄智星01笔记本电脑系统故障无法开机怎么办&#xff1f;有用户使用的玄派玄智星01笔记本突然出现了无法开机的情况。电脑正常开机之后&#xff0c;会一直卡在系统开机加载页面&#xff0c;无论等多久都无法进入到桌面上。那么这个情况要怎么去解决&#xff0c;来看看以下的…

非常特别的Toshiba Qosmio G55笔记本

非常特别的Toshiba Qosmio G55笔记本 Toshiba的Qosmio系列一向都是主打All-in-one&#xff0c;而这次所出的G55&#xff0c;最大的特色就是可以透过内置的Webcam镜头去感应手部的挥动&#xff0c;以执行多媒体方面的控制动作。因此&#xff0c;若在G55笔电面前来个「挥挥手&…

TOSHIBA笔记本无法开机

TOSHIBA L332笔记本无法开机 【问题描述】一台东芝笔记本打算暂不用电池&#xff0c;早上收电脑时拿掉电池&#xff0c;晚上接外接电源后开机后停在TOSHIBA LOGO画面不动了&#xff0c;硬盘灯在开机加点时闪一下后一直没反应&#xff0c;停止运转了。按F2进BIOS等很久很久才有反…

(第一章)OpGL超级宝典学习:配置和超级宝典相同的工作环境

目录 前言配套资源配置解压文件夹复制资源 HOWTOBUILD什么是CMake什么是GLFW安装CMake 开始构建build glfw生成debug和release的lib库 build sample 推送结语 前言 最近发现学习好像到了一定的瓶颈&#xff0c;马上要到2023年了&#xff0c;想要在新的一年开始后对自己有一定的…

Toshiba笔记本运行FC5时屏幕亮度调节方法

自己用的NB是M30,当时为这个问题苦恼了几天,Toshiba是用软调节的方式来实现亮度调节的,而官网上也没有对应的linux程序可供使用,虽然有另一种方法是通过命令行来调节亮度, 显示当前亮度等级: cat /proc/acpi/toshiba/lcd 设置亮度等级:(我的机器默认是从0到7,一共8个等级,设高了…

办公大师系列经典丛书 诚聘译者

办公软件大家都用过&#xff0c;里边到底还藏着多少功能&#xff0c;估计只有看过办公大师系列经典丛书的人才能说得明白。CSDN博客频道携手清华大学出版社诚邀天才的你&#xff0c;翻译本书。 一、活动时间&#xff1a; 2013年11月25日至2013年12月25日&#xff08;1个月&am…
最新文章