D. Jellyfish and Mex Codeforces Round 901 (Div. 2)
Problem - D - Codeforces
题目大意:有一个n个数的数组a,数m初始为0,每次操作可以删除任意一个数,然后m加上那个数,求n次操作和m的最小值
1<=n<=5000;0<=a[i]<=1e9
思路:可以发现,如果我们要删除某个数,那么一定要把所有和这个数相等的数全部删去,这样才能使MEX变小,同时,所有大于MEX的数删去的花费都是0,所以我们每次操作的数的大小都是递减的,且只会操作MEX到0。
那么我们令dp[i]等于MEX等于i时的最小花费,我们从MEX到0枚举i,同时枚举该删哪个数,也就是从0到i-1遍历,当前最小花费就是不删这个数dp[j],或者删这个数也就是dp[i]+当前MEX*(这个数数量-1)再加这个数,转移方程为dp[j]=min(dp[j],dp[i]+i*(cnt[j]-1)+j)
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 5;
ll n;
ll a[N];
ll cost[N];
ll cnt[N];
void init()
{for (int i = 0; i <= n; i++){cost[i] = 1e18;cnt[i] = 0;}
}
ll gcd(ll a, ll b)
{return b ? gcd(b, a % b) : a;
}
ll lowbit(ll x)
{return x & (-x);
}
void solve()
{ll m;cin >> n;init();for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] <= n){//MEX最大为n,大于n的都可以随便删cnt[a[i]]++;}}int mex = 0;while (cnt[mex]){//找当前的MEXmex++;}cost[mex] = 0;for (ll i = mex; i >= 0; i--){for (ll j = 0; j < i; j++){cost[j] = min(cost[j], cost[i] + i * (cnt[j] - 1) + j);}}cout << cost[0] << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}
相关文章:
D. Jellyfish and Mex Codeforces Round 901 (Div. 2)
Problem - D - Codeforces 题目大意:有一个n个数的数组a,数m初始为0,每次操作可以删除任意一个数,然后m加上那个数,求n次操作和m的最小值 1<n<5000;0<a[i]<1e9 思路:可以发现&am…...
操作系统内存管理相关
1. 虚拟内存 1.1 什么是虚拟内存 虚拟内存是计算机系统内存管理的一种技术,我们可以手动设置自己电脑的虚拟内存。不要单纯认为虚拟内存只是“使用硬盘空间来扩展内存“的技术。虚拟内存的重要意义是它定义了一个连续的虚拟地址空间,并且 把内存扩展到硬…...
Sui流动性质押黑客松获胜者公布,助力资产再流通
Sui流动质押黑客松于日前结束Demo Day演示,其中有五个团队获奖、六个团队荣誉提名,共有超过30个项目获得参赛资格。此外,有两个团队赢得了Sui上DeFi协议提供的赏金。 本次黑客松的目的是挖掘并奖励将流动质押功能集成到其apps和产品中的开发…...
为什么在使用PageHelper插件时,指定的每页记录数大小失效?显示所有的记录数
1.问题现象: 这里指定每页显示5条,却把所有的记录数都显示出来了 2.分析: 之前是可以的,然后发现:PageHelper.startPage(pageNum,pageSize) 和执行sql的语句 顺序颠倒了,然后就出错了。 3.验证…...
XML文档基础
什么是XML XML (eXtensible Markup Language,可扩展标记语言) 是一种用于存储和传输数据的文本文件格式。用户可以按照XML规则自定义标记,XML 的设计目标是传输数据,而不是显示数据,因此它是一种通用的标记语言,可用于…...
软考知识汇总-软件工程
软件工程 1 能力成熟度模型(CMM)2 能力成熟度模型集成(CMMI)2.1阶段式模型2.2 连续式模型 3 软件过程模型 1 能力成熟度模型(CMM) 将软件工程成熟度分为5个级别 初始级:杂乱无章,很…...
力扣:119. 杨辉三角 II(Python3)
题目: 给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 来源:力扣(LeetCode) 链接:力扣(LeetCode)…...
指针笔试题(带解析版)
题目2: struct MyStruct {int num;char* pcname;short sdate;char cha[2];short sba[4]; }*p; //结构体大小为32字节 //p0x100000 int main() {p 0x100000;printf("%p\n", p 0x1);//p:结构体指针,1下一个结构体指针,…...
服务器搭建(TCP套接字)-libevent版(服务端)
Libevent 是一个开源的事件驱动库,用于开发高性能、并发的网络应用程序。它提供了跨平台的事件处理和网络编程功能,具有高性能、可扩展性和可移植性。下面详细讲解 Libevent 的主要组成部分和使用方法。 一、事件基础结构(event_base&#x…...
斐波那契模型系列【动态规划】
动态规划步骤 1、状态表示 是什么:dp表(可能是一维或二维数组)里的值所表示的含义。 怎么来: 1、题目要求 2、经验题目要求 3、发现重复子问题 2、状态转移方程 dp[i]... 3、初始化 保证填表不越界 4、填表顺序 5、返回值 写代码时…...
【Java】微服务——Nacos注册中心
目录 1.Nacos快速入门1.1.服务注册到nacos1)引入依赖2)配置nacos地址3)重启 2.服务分级存储模型2.1.给user-service配置集群2.2.同集群优先的负载均衡 3.权重配置4.环境隔离4.1.创建namespace4.2.给微服务配置namespace 5.Nacos与Eureka的区别…...
Redis Cluster Gossip Protocol: PING, PONG, MEET
返回目录 PING / PONG / MEET 的发送 过程 计算freshNodes。freshNodes表示在消息中能携带的,在cluster节点字典中的节点总数,但需要减去myself和对端节点,因为myself的信息会存储在消息头中。实际上,并非所有在cluster节点字典…...
httpserver 下载服务器demo 以及libevent版本的 httpserver
实现效果如下: 图片可以直接显示 cpp h 这些可以直接显示 其他的 则是提示是否要下载 单线程 还有bug 代码如下 先放上来 #include "httpserver.h" #include "stdio.h" #include <stdlib.h> #include <arpa/inet.h> #include…...
构建强大的RESTful API:@RestController与@Controller的对比与应用
构建强大的RESTful API:RestController与Controller的对比与应用 前言什么是RESTful APIRestController,Controller,ResponseBody1. Controller注解:2. RestController注解:3. ResponseBody注解: 示例非thy…...
【Java-LangChain:使用 ChatGPT API 搭建系统-10】评估(下)-当不存在一个简单的正确答案时
第十章,评估(下)-当不存在一个简单的正确答案时 在上一章中,了解了如何评估 LLM 模型在 有明确正确答案 的情况下的输出,我们可以编写一个函数来判断 LLM 输出是否正确地分类并列出产品。 然而,如果 LLM …...
【微服务的集成测试】python实现-附ChatGPT解析
1.题目 微服务的集成测试 知识点:深搜 时间限制: 1s 空间限制: 256MB 限定语言:不限 题目描述: 现在有n个容器服务,服务的启动可能有一定的依赖性 (有些服务启动没有依赖)其次服务自身启动加载会消耗一些时间。 给你一个 nxn 的二维矩阵 useTime,其中 useTime[i][i]=10 表示…...
Mesa新版来袭
Mesa 17.1.6 发布了,Mesa 是一个三维(3D)图形库的开源集合,其主要目标是在 Linux / UNIX 操作系统下实现各种 API(应用程序编程接口)和 OpenGL 规范。 它面向 3D 计算机图形,硬件加速 3D 渲染和…...
基于 SpringBoot 2.7.x 使用最新的 Elasticsearch Java API Client 之 ElasticsearchClient
1. 从 RestHighLevelClient 到 ElasticsearchClient 从 Java Rest Client 7.15.0 版本开始,Elasticsearch 官方决定将 RestHighLevelClient 标记为废弃的,并推荐使用新的 Java API Client,即 ElasticsearchClient. 为什么要将 RestHighLevelC…...
辅助驾驶功能开发-功能对标篇(15)-NOA领航辅助系统-吉利
1.横向对标参数 厂商吉利车型FX11/EX11/DCY11/G636上市时间2022Q4方案6V5R+1DMS摄像头前视摄像头1*(8M)侧视摄像头/后视摄像头1环视摄像头4DMS摄像头1雷达毫米波雷达54D毫米波雷达/超声波雷达12激光雷达/域控供应商福瑞泰克辅助驾驶软件供应商福瑞泰克高精度地图百度芯片TDA4 T…...
javascript: Sorting Algorithms
// Sorting Algorithms int JavaScript https://www.geeksforgeeks.org/sorting-algorithms/ /** * file Sort.js * 1. Bubble Sort冒泡排序法 * param arry * param nszie */ function BubbleSort(arry, nszie) {var i, j, temp;var swapped;for (i 0; i < nszie - 1; i)…...
Keep架构深度解析:企业级AIOps告警管理平台的设计与实践
Keep架构深度解析:企业级AIOps告警管理平台的设计与实践 【免费下载链接】keep The open-source AIOps and alert management platform 项目地址: https://gitcode.com/GitHub_Trending/kee/keep Keep作为开源AIOps告警管理平台,采用现代化的微服…...
毕设项目分享 大数据共享单车数据分析与可视化(源码分享)
文章目录 0 前言1 课题背景2 数据清洗3 数据可视化热力图整体特征分布**查看2011-2012间的单车租借情况**天气对于租借数量的影响湿度与温度对于租借数量的影响注册用户与未注册用户 4 总结:5 最后 0 前言 🔥 这两年开始毕业设计和毕业答辩的要求和难度…...
在Windows上直接安装Android应用:APK安装器的三大优势与完整使用指南
在Windows上直接安装Android应用:APK安装器的三大优势与完整使用指南 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 你是否曾经希望在Windows电脑上直接运…...
Ruby纳米机器人框架:构建高内聚低耦合的自动化任务管道
1. 项目概述:当Ruby遇上纳米机器人最近在GitHub上闲逛,发现了一个名为icebaker/ruby-nano-bots的项目。这个标题本身就充满了想象力——Ruby,一门以优雅和生产力著称的动态语言;Nano-Bots,一个源自科幻、代表微观自动化…...
广义逆矩阵:从A+与A-的数学定义到工程求解实践
1. 广义逆矩阵:工程师的数学工具箱 第一次听说"广义逆矩阵"这个概念时,我正在处理一个推荐系统的评分预测问题。当时遇到一个头疼的情况:用户-物品评分矩阵极其稀疏,直接求逆根本行不通。导师轻描淡写地说:&…...
Burpsuite社区版实战指南:从零掌握渗透测试核心模块
1. Burpsuite社区版入门:环境搭建与基础配置 第一次接触Burpsuite时,我被它复杂的界面吓到了——满屏的英文标签、密密麻麻的功能按钮,还有那些看不懂的专业术语。但实际用下来发现,社区版的功能对新手非常友好。先说说下载安装&a…...
如何高效下载网易云音乐无损FLAC:完整指南与实战技巧
如何高效下载网易云音乐无损FLAC:完整指南与实战技巧 【免费下载链接】NeteaseCloudMusicFlac 根据网易云音乐的歌单, 下载flac无损音乐到本地.。 项目地址: https://gitcode.com/gh_mirrors/nete/NeteaseCloudMusicFlac 想要一键下载网易云音乐歌单中的无损…...
魔兽争霸3终极优化指南:WarcraftHelper 2024免费配置教程
魔兽争霸3终极优化指南:WarcraftHelper 2024免费配置教程 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 还在为经典游戏《魔兽争霸3》在现…...
从“能用”到“可靠”:基于SonarQube与Jenkins的代码质量防线构建实战
当测试覆盖率不再只是一串数字,而是合并代码前的“一票否决权” 1. 为什么你的“质量门禁”只是个摆设? 在很多团队的CI/CD流水线中,SonarQube的集成往往停留在“能跑就行”的阶段。流水线里确实有代码扫描这一步,日志里也打印出…...
3步掌握NBTExplorer:从Minecraft数据恐惧到编辑专家的完整指南
3步掌握NBTExplorer:从Minecraft数据恐惧到编辑专家的完整指南 【免费下载链接】NBTExplorer A graphical NBT editor for all Minecraft NBT data sources 项目地址: https://gitcode.com/gh_mirrors/nb/NBTExplorer 你是否曾经面对Minecraft的level.dat文件…...
