当前位置: 首页 > news >正文

[AHOI2018初中组] 分组---贪心算法

贪心没套路果真如此。

题目描述

小可可的学校信息组总共有 n 个队员,每个人都有一个实力值 ai​。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的 n 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不需要两个实力相同的选手。举个例子:[1,2,3,4,5] 是合法的分组方案,因为实力值连续;[1,2,3,5] 不是合法的分组方案,因为实力值不连续;[0,1,1,2] 同样不是合法的分组方案,因为出现了两个实力值为 1 的选手。

如果有小组内人数太少,就会因为时间不够而无法获得高分,于是小可可想让你给出一个合法的分组方案,满足所有人都恰好分到一个小组,使得人数最少的组人数最多,输出人数最少的组人数的最大值。

注意:实力值可能是负数,分组的数量没有限制。

输入格式

输入有两行:

第一行一个正整数 n,表示队员数量。
第二行有 n 个整数,第 i 个整数 ai​ 表示第 i 个队员的实力。

输出格式

输出一行,包括一个正整数,表示人数最少的组的人数最大值。

输入输出样例

输入 #1复制

7
4 5 2 3 -4 -3 -5

输出 #1复制

3

说明/提示

【样例解释】 分为 2 组,一组的队员实力值是 {4,5,2,3},一组是 {−4,−3,−5},其中最小的组人数为 3,可以发现没有比 3 更优的分法了。

【数据范围】

对于 100% 的数据满足:1≤n≤100000,∣ai​∣≤109。

本题共 10 个测试点,编号为 1∼10,每个测试点额外保证如下:

测试点编号数据限制
1∼2n≤6,1≤ai​≤100
3∼4n≤1000,1≤ai​≤105 且 ai​ 互不相同
5∼6n≤100000,ai​ 互不相同
7∼8n≤100000,1≤ai​≤10^5
9∼10n≤100000,−10^9≤ai​≤10^9

 思路:

从小到大排序,每组当出现不连续的数或前一个的个数比后一个的个数多时结束。

第二个是为什么?

我想的是:你多了可以给前面的组;但你少了,你若想向前方靠,那你前面比你多的数和后面的数会因你而分开(罪人),若想当头,和后面的在一起,那前面多的数就会……

代码: 

//忘记 2 2 3 3的情况
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, a[100005], m = 1;
int min0 = 9999999;
struct s {int i, w;
}b[100005];
void xunhuan(int i, int j) {//当后面的数个数没前面多时||断了,结束int z = i;z++;while (b[z].i + 1 == b[z + 1].i && z + 1 <= j) {if (b[z].w <= b[z + 1].w) {b[z].w--;m++;z++;}else {b[z].w--;m++;break;}}
}
int main(){cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}//输入数sort(a, a + n);//排序也可以用我之前写的归并排序int j = 0;for (int i = 0; i < n; i++) {//将相同的合并if (i == 0) {b[j].i = a[i];b[j].w = 1;}else {if (b[j].i == a[i]) {b[j].w++;}else {b[++j].i = a[i];b[j].w = 1;}}}m = 1;for (int i = 0; i <= j; i++) {if (b[i].i + 1 == b[i + 1].i&&i+1<=j) {if(b[i+1].w==1) {m++;}//连续且单一else {while(b[i + 1].w != 1){//不但一,防止该数的数量超过3xunhuan(i,j);min0 = min0 > m ? m : min0;m = 0;}m = 1;}}else {//不连续归零min0 = min0 > m ? m : min0;m = 1;}}cout << min0 << endl;return 0;
}

你可以用c来写,但归并手写有点多,所以偷个懒

相关文章:

[AHOI2018初中组] 分组---贪心算法

贪心没套路果真如此。 题目描述 小可可的学校信息组总共有 n 个队员&#xff0c;每个人都有一个实力值 ai​。现在&#xff0c;一年一度的编程大赛就要到了&#xff0c;小可可的学校获得了若干个参赛名额&#xff0c;教练决定把学校信息组的 n 个队员分成若干个小组去参加这场…...

知识图谱-学习计划

✨知识图谱知识学习&#xff0c;给我点赞&#xff01;&#x1f31f;&#x1f31f;&#x1f31f; &#x1f31f;什么是知识图谱&#xff1f; 知识图谱是一种通过图结构表示知识的技术&#xff0c;它可以帮助我们更清晰地理解和组织信息。无论是学习、工作还是生活&#xff0c;知…...

网安作业3

标准版 接口ip配置 r2 [r2]interface GigabitEthernet 0/0/0 [r2-GigabitEthernet0/0/0]ip address 13.0.0.3 24 [r2-GigabitEthernet0/0/0]interface GigabitEthernet 0/0/1 [r2-GigabitEthernet0/0/1]ip address 100.1.1.254 24 [r2-GigabitEthernet0/0/1]interface Gigab…...

快速提升网站收录:内容创作的艺术

快速提升网站收录&#xff0c;内容创作是关键。以下是一些关于内容创作以提升网站收录的艺术性建议&#xff1a; 一、关键词研究与优化 选择长尾关键词&#xff1a;进行深入的关键词研究&#xff0c;选择既符合网站主题又具有一定搜索量的长尾关键词。这些关键词通常更具体&a…...

【C语言】CreateFile函数用法介绍

目录 一、函数原型与基本功能 二、参数详解 1. lpFileName&#xff08;文件路径&#xff09; 2. dwDesiredAccess&#xff08;访问权限&#xff09; 补充说明 3. dwShareMode&#xff08;共享模式&#xff09; 5. dwCreationDisposition&#xff08;创建策略&#xff09…...

蓝桥杯好数

样例输入&#xff1a; 24 输出&#xff1a;7 输入&#xff1a;2024 输出&#xff1a; 150 思路&#xff1a;本题朴素方法的时间复杂度是O(n * log10(n)) &#xff0c;不超时。主要考察能否逐位取数&#xff0c;注意细节pi&#xff0c;这样不会改变i,否则会导致循环错误。 #in…...

SOME/IP--协议英文原文讲解10

前言 SOME/IP协议越来越多的用于汽车电子行业中&#xff0c;关于协议详细完全的中文资料却没有&#xff0c;所以我将结合工作经验并对照英文原版协议做一系列的文章。基本分三大块&#xff1a; 1. SOME/IP协议讲解 2. SOME/IP-SD协议讲解 3. python/C举例调试讲解 4.2.2 Req…...

欢乐力扣:赎金信

文章目录 1、题目描述2、 代码 1、题目描述 赎金信&#xff0c;给你两个字符串&#xff1a;ransomNote 和 magazine &#xff0c;判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以&#xff0c;返回 true &#xff1b;否则返回 false 。magazine 中的每个字符只能在…...

【量化科普】Standard Deviation,标准差

【量化科普】Standard Deviation&#xff0c;标准差 &#x1f680;&#x1f680;&#x1f680;量化软件开通&#x1f680;&#x1f680;&#x1f680; &#x1f680;&#x1f680;&#x1f680;量化实战教程&#x1f680;&#x1f680;&#x1f680; 在量化投资领域&#xf…...

stm32单片机个人学习笔记15(I2C通信协议)

前言 本篇文章属于stm32单片机&#xff08;以下简称单片机&#xff09;的学习笔记&#xff0c;来源于B站教学视频。下面是这位up主的视频链接。本文为个人学习笔记&#xff0c;只能做参考&#xff0c;细节方面建议观看视频&#xff0c;肯定受益匪浅。 STM32入门教程-2023版 细…...

网络安全防护

一&#xff1a;物理安全防护 直接的物理破坏所造成的损失远大于通过网络远程攻击 提高物理安全需关注的问题&#xff1a; 1: 服务器和安全设备是否放置在上锁的机房内&#xff1f; 2: 网络设备是否被保护和监控&#xff1f; 3: 是否有无关人员单独在敏感区域工作&…...

YOLOV7的复现过程

复现 YOLOv7 代码的步骤相对清晰&#xff0c;主要分为以下几个部分&#xff1a; 环境准备克隆 YOLOv7 仓库准备数据集训练模型验证和测试推理&#xff08;Inference&#xff09; 下面是一个简化的流程来帮助你复现 YOLOv7 代码&#xff1a; 1. 环境准备 首先&#xff0c;你…...

uniapp实现app的pdf预览

实现效果 文件准备 static下添加该pdf文件&#xff08;下载地址&#xff1a;https://gitee.com/shallow-winds/resource_package/tree/master/%E6%96%B9%E6%B3%95%E4%B8%80/html&#xff09; 使用web-view进行展示&#xff1a; 在这里插入代码片 <web-view :src"u…...

用Java创建一个验证码的工具类

在Java中创建一个验证码工具类&#xff0c;可以通过以下代码实现。该工具类支持生成包含字母和数字的随机验证码图片&#xff0c;并添加干扰线和噪点以提高安全性。以下是详细实现&#xff1a; 完整代码实现 import javax.imageio.ImageIO; import java.awt.*; import java.aw…...

uvm中的激励是如何发送出去的

在UVM中&#xff0c;Sequence生成的激励&#xff08;Transaction&#xff09;通过以下协作流程发送到Driver并最终驱动到DUT&#xff0c;其核心机制如下&#xff1a; --------------- --------------- ------------ ----- | Sequence | → | Seque…...

一只企鹅如何改变世界

一、历史的转折点:一只企鹅如何改变世界 1991年,芬兰大学生Linus Torvalds在邮件列表中写道:“我正在做一个自由的操作系统(只是爱好,不会像GNU那样庞大专业)”。这个后来被称为Linux内核的项目,与GNU项目的结合,点燃了开源运动的燎原之火。 关键演化: 1996年:Tux企…...

拦截器VS过滤器:Spring Boot中请求处理的艺术!

目录 一、拦截器&#xff08;Interceptor&#xff09;和过滤器&#xff08;Filter&#xff09;&#xff1a;都是“守门员”&#xff01;二、如何实现拦截器和过滤器&#xff1f;三、拦截器和过滤器的区别四、执行顺序五、真实的应用场景六、总结 &#x1f31f;如果喜欢作者的讲…...

C语言预处理学习笔记

1. 预处理器的功能 预处理器&#xff08;Preprocessor&#xff09;在编译C语言程序之前对源代码进行预处理。预处理指令以#号开头&#xff0c;主要包括文件包含、宏定义、条件编译等功能。 2. 文件包含 文件包含功能用于在一个文件中包含另一个文件的内容&#xff0c;通常用…...

LLM基础环境准备-云服务器

软件环境 腾讯云 操作系统&#xff1a; TencentOS Server 3.1 (TK4) Python: 3.9.0(使用 conda的虚拟python环境&#xff0c;可根据实际需要更换版本&#xff0c;当前使用的是3.9.0的版本) CUDA Version: 12.2&#xff08;腾讯云会自动安装&#xff09; Driver Version: 5…...

网络协议相关知识有哪些?

前言 网络协议的基础是OSI和TCP/IP模型,这两个模型是理解协议分层的关键。 正文(仅是个人理解,如有遗漏望海涵) 网络协议是网络中设备间通信的规则和标准,涉及数据传输、路由、错误控制等多个方面。以下是网络协议相关知识的系统梳理: 一、网络协议分层模型 1、OSI七…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

Qt的学习(二)

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...