E. Beautiful Array(cf954div3)

题意:给定一个数组,可以先对数组进行任意排序,每次操作可以选择一个ai,将它变成ai+k,

想让这个数组变成一个美丽数组(回文数组),求最少操作次数

分析:

先找出相同的数字,去掉;将取模相同的放一块,如果取模不同,无论怎么加他们都一定不会相等。放一块之后,会有两种情况,一种是偶数个,一种是奇数个。如果是偶数个,先排序,每每相邻两个可以求出最小操作次数。如果是奇数,如果只有一个数就直接放最中心,否则还要判断谁放在最中心。枚举删掉哪个数,然后前后缀和算出最小答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){
    int n,k;cin>>n>>k;
    map<int,int>mp;int t;
    for(int i=1;i<=n;i++){
        cin>>t;mp[t]++;
    }
    vector<int>a;
    for(auto&[x,y]:mp){
        if(y%2!=0){
            a.push_back(x);
        }
    }
    if(a.size()<=1){
        cout<<"0"<<endl;
        return;
    }
    map<int,vector<int>>rec;
    for(int i=0;i<a.size();i++){
        int c=a[i];
        rec[c%k].push_back(c);
    }
    ll ans=0;
    int cnt=0;
    
    for(auto& [x,cur]:rec){    
        int f=1;//0为奇数,1为偶数
        if(cur.size()%2!=0){
            cnt++;f=0;
            if(cnt>1){
            cout<<"-1"<<endl;
            return;    
            }
        }
        if(f==1){//如果是偶数
            sort(cur.begin(),cur.end());
            for(int i=1;i<cur.size();i+=2){
                ans+=(cur[i]-cur[i-1])/k;
            }
        }
        else if(cur.size()>1){//长度大于1的奇数个    
            sort(cur.begin(),cur.end());
            int m=cur.size();
            cnt++;
            vector<ll>p(m,0);
            vector<ll>s(m,0);
            p[1]=cur[1]-cur[0];
            for(int i=3;i<m;i+=2){
                p[i]=p[i-2]+cur[i]-cur[i-1];
            }
            s[m-2]=cur[m-1]-cur[m-2];
            for(int i=m-4;i>=0;i-=2){
                s[i]=s[i+2]+cur[i+1]-cur[i];
            }
            ll mi=min(p[m-2],s[1]);
            for(int i=2;i<m-2;i+=2){
                mi=min(mi,p[i-1]+s[i+1]);
            }
            ans+=mi/k;
        }
    }
    cout<<ans<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)sol();
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STM32 - PWR 笔记

PWR&#xff08;Power Control&#xff09;电源控制 PWR 负责管理 STM32 内部的电源供电部分&#xff0c;可以实现 可编程电压监测器 和 低功耗模式 的功能 可编程电压监测器&#xff08;PVD&#xff09;可以监控VDD电源电压&#xff0c;当VDD下降到PVD阀值以下或上升到PVD…

Apache Flink 运行时架构

Flink 运行时架构 Flink整个系统由两个主要部分组成JobManager和TaskManager&#xff0c;Flink架构也遵循Master-Slave架构设计原则&#xff0c;JobManager为Master节点&#xff0c;TaskManager为worker&#xff08;Slave&#xff09;节点&#xff0c;所有组件之间通讯都是借助…

项目进度管理(5-1)常见的缓冲区监控方法

缓冲区监控是一种项目管理技术&#xff0c;主要用于关键链项目管理系统&#xff08;Critical Chain Project Management, CCPM&#xff09;中。它的核心理念是识别和管理项目中的不确定性和依赖性&#xff0c;以提高项目完成的可靠性。 缓冲区监控方法主要是针对项目进度计划执…

【ChatGPT 消费者偏好】第二弹:ChatGPT在日常生活中的使用—推文分享—2024-07-10

今天的推文主题还是【ChatGPT & 消费者偏好】 第一篇&#xff1a;哪些动机因素和技术特征的组合能够导致ChatGPT用户中高和低的持续使用意图。第二篇&#xff1a;用户对ChatGPT的互动性、性能期望、努力期望以及社会影响如何影响他们继续使用这些大型语言模型的意向&#x…

OpenCV中使用Canny算法在图像中查找边缘

操作系统&#xff1a;ubuntu22.04OpenCV版本&#xff1a;OpenCV4.9IDE:Visual Studio Code编程语言&#xff1a;C11 算法描述 Canny算法是一种广泛应用于计算机视觉和图像处理领域中的边缘检测算法。它由John F. Canny在1986年提出&#xff0c;旨在寻找给定噪声条件下的最佳边…

Elasticsearch:使用 Filebeat 从 Node.js Web 应用程序提取日志

本指南演示了如何从 Node.js Web 应用程序中提取日志并将其安全地传送到 Elasticsearch Service 部署中。你将设置 Filebeat 来监控具有标准 Elastic Common Schema (ECS) 格式字段的 JSON 结构日志文件&#xff0c;然后在向 Node.js 服务器发出请求时&#xff0c;你将在 Kiban…

three-tile: 1. 第一个three-tile程序

上篇介绍了&#xff1a;three-tile&#xff1a; 一个开源的轻量级三维瓦片库-CSDN博客 three-tile 是一个开源的轻量级三维瓦片库&#xff0c;它基于threejs使用typescript开发&#xff0c;提供一个三维地形模型&#xff0c;能轻松给你的应用增加三维瓦片地图。 项目地址&…

Spark-RDD和共享变量

概览 每个Spark应用程序都由一个driver program 组成&#xff0c;该驱动程序运行我们编写的main函数&#xff0c;并在集群上执行各种 并行 操作。Spark提供的主要抽象是一个 弹性分布式数据集&#xff08;RDD&#xff09;&#xff0c;它是一个跨集群节点分区的元素集合&#x…

maven7——(重要,构建项目)maven项目构建(命令)

Maven的常用命令管理项目的生命周期 clean命令 清除编译产生的target文件夹内容&#xff0c;可以配合相应命令在cmd中使用&#xff0c;如mvn clean package&#xff0c; mvn clean test D:\工作\公司培训-4班\day20\day20\untitled1>mvn clean compile命令 该命令可以…

Nginx: Rewrite功能配置/Nginx反向代理/Nginx的安全控制SSL

Rewrite功能配置 Rewrite是Nginx服务器提供的一个重要基本功能&#xff0c;是Web服务器产品中几乎必备的功能。主要的作用是用来实现URL的重写。www.jd.com 注意:Nginx服务器的Rewrite功能的实现依赖于PCRE的支持&#xff0c;因此在编译安装Nginx服务器之前&#xff0c;需要安…

[ICS] Inferno(地狱) ETH/IP未授权访问,远程控制工控设备利用工具

项目地址:https://github.com/MartinxMax/Inferno Inferno $ ./Install.sh $ python Inferno.py -h 模拟服务端 $ sudo python3 -m pip install --upgrade cpppo $ $ python -m cpppo.server.enip SCADAINT[1000] ADMININT[2] -v 创建一个EtherNet/IP设备 扫描设备 $ pyth…

【网络安全】Oracle:SSRF获取元数据

未经许可&#xff0c;不得转载。 文章目录 前言正文漏洞利用 前言 Acme 是一家广受欢迎的播客托管公司&#xff0c;拥有庞大的客户群体。与许多大型运营公司一样&#xff0c;Acme 采用了Apiary的服务&#xff0c;使用户能够安全高效地管理他们的播客。 Apiary 于2017年初被Or…

【Django项目】基于Python+Django+MySQL的音乐网站系统项目

功能介绍 首页&#xff1a;歌曲分类、歌曲搜索、热门歌曲、热门下载、新歌推荐 歌曲排行&#xff1a;歌曲分类、分页功能 用户板块&#xff1a;用户登陆/注册、播放历史 歌曲详情&#xff1a;歌曲播放、当前播放列表、歌曲点评、歌曲播放插件、下载歌曲 系统后台&#xff1a;歌…

如何将Docker镜像源更改为阿里云的镜像加速地址

在使用Docker时&#xff0c;尤其是在国内环境下&#xff0c;由于网络原因&#xff0c;从Docker Hub拉取镜像可能会遇到速度较慢的问题。为了提高拉取速度&#xff0c;我们可以将Docker的镜像源更改为阿里云等国内镜像源。下面详细介绍如何获取并配置阿里云的Docker镜像加速地址…

【中项第三版】系统集成项目管理工程师 | 第 4 章 信息系统架构⑤ | 4.8 - 4.9

前言 第4章对应的内容选择题和案例分析都会进行考查&#xff0c;这一章节属于技术相关的内容&#xff0c;学习要以教材为准。本章分值预计在4-5分。 目录 4.8 云原生架构 4.8.1 发展概述 4.8.2 架构定义 4.8.3 基本原则 4.8.4 常用架构模式 4.8.5 云原生案例 4.9 本章…

docker(六)--创建镜像

六、创建镜像 1.创建镜像两种方式 方式1&#xff1a; 更新镜像 docker commit 方式2&#xff1a;构建镜像 docker build 2.更新镜像 1&#xff09;用法 docker commit -m“描述信息” -a作者 容器id或者容器名 镜像名:tag 2&#xff09;步骤 ①根据镜像运行容器 ②进入容…

栈和队列题目详解

前言&#xff1a; 在前面我们学习了栈和队列&#xff0c;栈的特性是后进先出&#xff0c;队列的特性是先进先出&#xff0c;当我们了解了这些之后&#xff0c;我们就可以用到栈和队列的特性来简单的做一些题目了。 1. 有效的括号 有效的括号&#xff1a;. - 力扣&#xff08…

YOLOv10改进 | Conv篇 | 利用FasterBlock二次创新C2f提出一种全新的结构(全网独家首发,参数量下降70W)

一、本文介绍 本文给大家带来的改进机制是利用FasterNet的FasterBlock改进特征提取网络&#xff0c;将其用来改进ResNet网络&#xff0c;其旨在提高计算速度而不牺牲准确性&#xff0c;特别是在视觉任务中。它通过一种称为部分卷积&#xff08;PConv&#xff09;的新技术来减少…

火柴棒图python绘画

使用Python绘制二项分布的概率质量函数&#xff08;PMF&#xff09; 在这篇博客中&#xff0c;我们将探讨如何使用Python中的scipy库和matplotlib库来绘制二项分布的概率质量函数&#xff08;PMF&#xff09;。二项分布是统计学中常见的离散概率分布&#xff0c;描述了在固定次…

夏日智启:我的Datawhale AI夏令营探索之旅

前言 最近几年&#xff0c;AI&#xff08;人工智能&#xff09;的发展呈现出了前所未有的迅猛势头&#xff0c;其影响力和应用范围不断扩大&#xff0c;深刻地改变着我们的生活、工作和社会结构。尤其是AI大模型技术&#xff0c;国内外可谓是“百模大战”&#xff0c;百舸争流…