放学辣[简单版]
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述
本题和 D 题的唯一区别是 NNN 的范围。
校园里目前有 NNN 名学生,这些学生属于 MMM 个班级。第 iii(i=1,2,...,Ni = 1,2,...,Ni=1,2,...,N)个人属于第 AiA_iAi 个班级。突然,放学铃声响起,你还没来得及思索,就已经有 KKK 名学生已经冲出了学校。然而,由于某班级的老师还在拖堂,可以确定这个班级目前还没有任何学生离校。现在请你求出,假设恰好只有班级 jjj(j=1,2,...,Mj = 1,2,...,Mj=1,2,...,M)的老师还在拖堂,在剩下的未拖堂的班级中,还留在学校的人数最多的班级的最少的可能人数是多少。
输入描述:
第一行三个正整数 NNN(1≤N≤1021 \leq N\leq 10^21≤N≤102),MMM(1≤M≤N1 \leq M\leq N1≤M≤N),KKK(1≤K≤N1 \leq K\leq N1≤K≤N)含义如上所述。
第二行 NNN 个正整数 AiA_iAi(1≤Ai≤M1 \leq A_i\leq M1≤Ai≤M),含义如上所述。
输出描述:
M 个整数,第 i 个整数表示恰好只有班级 i 的老师还在拖堂,在剩下的未拖堂的班级中,还留在学校的人数最多的班级的最少的可能人数是多少。如果班级 i 拖堂就不可能有 K名学生冲出学校,则输出 -1。
示例1
输入
6 3 3
3 1 2 3 3 2
输出
1 1 0
示例2
输入
6 3 4
3 1 2 3 3 2
输出
1 0 -1
其实这个题完全是因为思路被带偏了。前面有一道差不多的题目,我用的map加上匿名函数排序过的(中途sort忘记加cmp参数WA了一发),然后这一题也想这样做,只是每次那一个earse了当前班级的副本去运算,本来这个思路是对的,但是后面到具体的放人的环节模拟错了,我是将所有的班级当成整体看,正确解法应当要用优先队列维护每个班级的人数,从最多的人的合法班级里面放一个走,然后维护队列
先放我的错误解法吧,特例都对了,就是不知道错哪了
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
// #define DEBUG true
int n,m,k;
// 拖堂的班级的人数
int normalNums=0;//调用可以进行重定向
void initRedict(){#ifdef DEBUGcout<<"执行重定向"<<endl; //重定向输入 freopen("../redict/demo/demo_in.txt","r",stdin); //重定向输出 覆写
// freopen("../redict/demo/demo_out.txt","w",stdout); #endif
}
// 调用可以取消重定向
void breakEnd(){#ifdef DEBUGfclose(stdin);fclose(stdout); #endif
}bool cmp(const pair<int,int>& a,const pair<int,int>& b){return a.second<b.second;
}int judge(int nums){if (nums&1) return 1;return 0;
}
void solved(map<int,int> mymap){
// 自由班级最多人数 map<int,int>::iterator iter=max_element(mymap.begin(),mymap.end(),cmp);int maxValue=iter->second;// 统计第二大的班级人数 mymap.erase(iter->first);int secondMaxValue= max_element(mymap.begin(),mymap.end(),cmp)->second;// 获取最小int minValue= min_element(mymap.begin(),mymap.end(),cmp)->second;
// cout<<maxValue<<" 打水印"<<endl;int nowTotalNums=n-normalNums;if (maxValue-secondMaxValue>k){cout<<maxValue-secondMaxValue;}else if (nowTotalNums>=k){
// secondMaxValue不够大
// cout<<"打印k a b"<<k<<" "<<maxValue<<" "<<secondMaxValue<<" "<<endl;
// if (nowTotalNums>k) cout<<"1"; cout<<secondMaxValue-(k-(maxValue-secondMaxValue))/2;
// if (secondMaxValue-(k-(maxValue-secondMaxValue))/2>minValue){
// cout<<secondMaxValue-(k-(maxValue-secondMaxValue))/2;
// }
// else{
// cout<<minValue;
// }}else{cout<<"-1";}cout<<" ";
// // 又没有超过其他小班的人数和
// if (k<=nowTotalNums-maxValue){
// cout<< maxValue-normalNums;
// }
// else{
// cout<<n-k-normalNums;
// }}
map<int,int> mymap;
int main(){initRedict();cin>>n>>m>>k;for(int i=0;i<n;i++){int nums;cin>>nums;mymap[nums]++;}for(int i=1;i<=m;i++){map<int,int> tempMap=mymap;normalNums=tempMap[i]; tempMap.erase(i);solved(tempMap);}return 0;
}
下面是合理的思路,就是简单考察对数据结构的运用,而不是算法考察!!!
#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
//#define DEBUG true
int n,m,k;
// 拖堂的班级的人数
int normalNums=0;//调用可以进行重定向
void initRedict(){#ifdef DEBUGcout<<"执行重定向"<<endl; //重定向输入 freopen("../redict/demo/demo_in.txt","r",stdin); //重定向输出 覆写
// freopen("../redict/demo/demo_out.txt","w",stdout); #endif
}
// 调用可以取消重定向
void breakEnd(){#ifdef DEBUGfclose(stdin);fclose(stdout); #endif
}map<int,int> mymap;
int main(){initRedict();cin>>n>>m>>k;for(int i=0;i<n;i++){int nums;cin>>nums;mymap[nums]++;}bool flag=false;for(int i=1;i<=m;i++){
// if (mymap[i]+k>n){if (flag) cout<<" ";cout<<"-1";flag=true;continue;}
// 我们需要一个升序的结构 priority_queue<int ,vector<int>,less<int> >myqueue; // 开始统计 使用优先队列即可for(int j=1;j<=m;j++){if (i-j){myqueue.push(mymap[j]);}} // 开始进行放人 从最多的开始放int coun=k;
// cout<<coun<<endl; while(coun--){int classNums=myqueue.top();myqueue.pop();myqueue.push(classNums-1);} if (flag) cout<<" ";cout<<myqueue.top();flag=true;}return 0;
}
相关文章:
放学辣[简单版]
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 题目描述 本题和 D 题的唯一区别是 NNN 的范围。 校园里目前有 NNN 名学生,这些学生属于 MMM 个班级。第 iii(i1,2,...,Ni 1,2,...,Ni1,2,...,N)个人属于第…...
面向对象设计——原型模式
原型设计模式是一种创建型设计模式,其主要目标是创建对象的新实例,同时尽量减少与使用者的交互,以降低对象创建的复杂性。这通过复制(或克隆)现有对象的实例来实现,以获得新对象,而不是通过实例化类来创建。 以下是原型设计模式的关键概念: 原型接口(Prototype Inter…...
SpringAOP源码解析之advice执行顺序(三)
上一章我们分析了Aspect中advice的排序为Around.class, Before.class, After.class, AfterReturning.class, AfterThrowing.class,然后advice真正的执行顺序是什么?多个Aspect之间的执行顺序又是什么?就是我们本章探讨的问题。 准备工作 既…...
CentOS 安装 tomcat 并设置 开机自启动
CentOS 安装 tomcat 并设置 开机自启动 下载jdk和tomcat curl https://download.oracle.com/java/21/latest/jdk-21_linux-x64_bin.tar.gz curl https://dlcdn.apache.org/tomcat/tomcat-10/v10.1.15/bin/apache-tomcat-10.1.15.tar.gz解压jdk和tomcat并修改目录名称 tar -z…...
论文阅读——ELECTRA
论文下载:https://openreview.net/pdf?idr1xMH1BtvB 另一篇分析文章:ELECTRA 详解 - 知乎 一、概述 对BERT的token mask 做了改进。结合了GAN生成对抗模型的思路,但是和GAN不同。 不是对选择的token直接用mask替代,而是替换为…...
Android开发知识学习——HTTP基础
文章目录 学习资源来自:扔物线HTTPHTTP到底是什么HTTP的工作方式URL ->HTTP报文List itemHTTP的工作方式请求报文格式:Request响应报文格式:ResponseHTTP的请求方法状态码 HeaderHostContent-TypeContent-LengthTransfer: chunked (分块传…...
51单片机的hello world之点灯
文章目录 前言一、基础定义和点灯二、延时函数三、独立按键三、中断的配置和使用外部中断法捕获中断 总结 前言 hello 大家好这里是夏目学长的51单片机课堂,本篇博客是夏目学长观看B站up主学电超人的视频所写的一篇51单片机入门博客之51单片机点灯以及 独立按键 中…...
Django 实战开发(一)项目搭建
1.项目搭建 用pycharm 编辑器可以直接 New 一个 Django 项目 2.新建应用 python manage.py startapp demo项目结构如下: 3.编写第一个Django 视图函数 /demo/views: from django.http import HttpResponse def welcome(request):return HttpResponse("welcome to dja…...
Unity把余弦值转成弧度和角度
Vector3 RoleForwardV MainRole.transform.forward; Vector3 RoleToMonsterV Monster.transform.position - MainRole.transform.position; float DotResult Vector3.Dot(RoleForwardV, RoleToMonsterV.normalized);//点乘两个单位向量 Mathf.Acos(DotResult); //--它计…...
debian、ubuntu打包deb包工具,图形界面deb打包工具mkdeb
debian、ubuntu打包deb包工具,图形界面deb打包工具mkdeb,目前版本1.0 下载地址: 链接:https://pan.baidu.com/s/1QX6jXNMYRybI9Cx-1N_1xw?pwd8888 md5: b6c6658408226a8d1a92a7cf93834e66 mkdeb_1.0-1_all.deb...
微信小程序如何使用地球半径计算两组经纬度点之间的距离(自身位置与接口返回位置)【上】
目录 1.配置位置权限 2.获取当前自身经纬度 3. 请求接口拿到返回经纬 4. 循环取每一项的经纬 5.如何判断是否打开了定位权限 6.进行距离计算操作 7.运行效果 8.完整代码 首先在使用小程序时,请求的接口一定要去配置合法域名,才能够进行接下来…...
postgis ST_ClipByBox2D用法
官方文档 概述 geometry ST_ClipByBox2D(geometry geom, box2d box); 描述 以快速且宽松但可能无效的方式通过 2D 框剪切几何体。 拓扑上无效的输入几何图形不会导致抛出异常。 不保证输出几何图形有效(特别是,可能会引入多边形的自相交)…...
【MyBatis Plus】深入探索 MyBatis Plus 的条件构造器,自定义 SQL语句,Service 接口的实现
文章目录 前言一、条件构造器1.1 什么是条件构造器1.2 QueryWrapper1.3 UpdateWrapper1.4 LambdaWrapper 二、自定义 SQL 语句2.1 自定义 SQL 的基本用法2.2 自定义 SQL 实现多表查询 三、Service 接口3.1 对 Service 接口的认识3.2 实现 Service 接口3.3 实现增删改查功能3.4 …...
基于AI与物联网技术的智能视频监控系统架构剖析
智能视频监控系统正逐渐成为我们日常生活和工作中不可或缺的一部分。基于物联网的智能监控系统架构为我们在各个领域提供了更高效、智能化和安全的监控解决方案。本文将以旭帆科技EasyCVR视频监控云平台为例,介绍基于AI、物联网的智能监控系统的架构,并探…...
mysql 基础知识
MySQL 是一种关系型数据库,在Java企业级开发中非常常用,因为 MySQL 是开源免费的,并且方便扩展。阿里巴巴数据库系统也大量用到了 MySQL,因此它的稳定性是有保障的。MySQL是开放源代码的,因此任何人都可以在 GPL(Gener…...
Flink CDC 2.0 主要是借鉴 DBLog 算法
DBLog 算法原理 DBLog 这个算法的原理分成两个部分,第一部分是分 chunk,第二部分是读 chunk。分 chunk 就是把一张表分为多个 chunk(桶/片)。我可以把这些 chunk 分发给不同的并发的 task 去做。例如:有 reader1 和 re…...
win10 + VS2017 编译libjpeg(jpeg-9b)--更新
刚刚写了一篇“win10 VS2017 编译libjpeg(jpeg-9b)”, 然后就发现,还有一个更好的方法。因此,重新更新了一篇,作为对比与参考。 需要用到的文件: jpeg-9b.zip win32.mak 下载链接链接…...
使用pycharm远程调试
使用pycharm 专业版, 在设置解释器中,具备ssh 解释器功能; 一般在本地无法调试远程端代码,机械性的scp传输文件十分影响工作效率,PyCharm的Pro支持远程Run,Debug,等可视化的功能。 操作系统&…...
rust学习
rust学习 String类型clone和copy结构体的内存分布for循环(<font color red>important!)堆和栈数据结构vector panic失败就 panic: unwrap 和 expect传播错误 模式匹配忽略模式的值绑定 泛型特征Trait定义特征为类型实现特征孤儿规则使…...
GCC、g++、gcc的关系
GCC、g、gcc的关系 引言 VsCode中对编译环境进行配置的时选择编译器时发现有多种不同的编译器 GNU计划和GCC GNU的全称 GNU’s Not UNIX GNU是一个计划 Q:为什么会有这个计划 因为当时的Unix开始收费和商业闭源,有人觉得不爽→ 想要自己开发和Unix类似的→GNU计划 GUN计划目…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
