放学辣[简单版]
链接:登录—专业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计划目…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
