1056. Mice and Rice (25)-PAT甲级真题
当时没想到可以用队列来做,就傻傻的模拟了,用cur存当前轮的id,这个id对应的是order的下标,这里有个求rank的技巧就是当前轮没有晋级的rank为(当前轮的组数+1)
模拟:
#include<bits/stdc++.h>
using namespace std;
struct node{int id,w,rk=0;
};
vector<node> vec;
vector<int> order,cur; //cur用来记录当前晋级的组里面的id,对应order数组的下标
int np,ng;
bool cmp(node&a, node& b){return a.rk>b.rk;
}
int main(){scanf("%d%d",&np,&ng);vec.resize(np);order.resize(np);cur.resize(np);for(int i=0;i<np;i++){scanf("%d",&vec[i].w);vec[i].id=i;cur[i]=i;}for(int i=0;i<np;i++)scanf("%d",&order[i]);if(cur.size()==1){printf("1");return 0;}while(cur.size()>1){int start=0;vector<int> temp;int numg; //当前分组数if(cur.size()%ng!=0) numg=cur.size()/ng+1;else numg=cur.size()/ng;while(start<cur.size()){int max=-1,maxi=0;for(int i=start;i<start+ng&&i<cur.size();i++){vec[order[cur[i]]].rk=numg+1;if(max<vec[order[cur[i]]].w){max=vec[order[cur[i]]].w;maxi=i;}}vec[order[cur[maxi]]].rk=numg==1?1:numg+1;temp.push_back(cur[maxi]);start+=ng;}cur=temp;}sort(vec.begin(),vec.end(),[](node& a,node& b){return a.id<b.id;});for(int i=0;i<vec.size();i++)printf(i==0?"%d":" %d",vec[i].rk);return 0;
}
柳神的队列做法:
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node {int weight, index, rank, index0;
};
bool cmp1(node a, node b) {return a.index0 < b.index0;
}
int main() {int n, g, num;scanf("%d%d", &n, &g);vector<int> v(n);vector<node> w(n);for(int i = 0; i < n; i++)scanf("%d", &v[i]);for(int i = 0; i < n; i++) {scanf("%d", &num);w[i].weight = v[num];w[i].index = i;w[i].index0 = num;}queue<node> q;for(int i = 0; i < n; i++)q.push(w[i]);while(!q.empty()) {int size = q.size();if(size == 1) {node temp = q.front();w[temp.index].rank = 1;break;}int group = size / g;if(size % g != 0)group += 1;node maxnode;int maxn = -1, cnt = 0;for(int i = 0; i < size; i++) {node temp = q.front();w[temp.index].rank = group + 1;q.pop();cnt++;if(temp.weight > maxn) {maxn = temp.weight;maxnode = temp;}if(cnt == g || i == size - 1) {cnt = 0;maxn = -1;q.push(maxnode);}}}sort(w.begin(), w.end(), cmp1);for(int i = 0; i < n; i++) {if(i != 0) printf(" ");printf("%d", w[i].rank);}return 0;
}
相关文章:
1056. Mice and Rice (25)-PAT甲级真题
当时没想到可以用队列来做,就傻傻的模拟了,用cur存当前轮的id,这个id对应的是order的下标,这里有个求rank的技巧就是当前轮没有晋级的rank为(当前轮的组数1) 模拟: #include<bits/stdc.h&g…...
色轮在数据可视化中的应用
在数据可视化中,色彩的运用不仅仅是为了美观,更是为了传达信息、区分数据和提升图表的易读性。本文探讨色轮及其色彩公式的应用,帮助大家更好地运用色彩来提升数据可视化的效果。 1、色轮的基础概念 色轮是一个用于表示颜色之间关系的图形工…...
编程-设计模式 8:组合模式
设计模式 8:组合模式 定义与目的 定义:组合模式又称为部分-整体模式,它允许你将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。目的:该模式的主要目的是将多个对象…...
c语言指针(8.11)
那这样p和*p记录的地址不一样了吗? 不,p 和 *p 记录的地址在某种意义上是“相同”的,但它们在类型和使用方式上有所不同。 p 的地址:p 是一个指针,它本身存储了一个地址,这个地址是二维数组 arr 的第一行&a…...
加密技术的发展
加密是一种用于保护数据安全的技术,通过将原始信息(明文)转换为一种不可读的形式(密文),确保只有拥有正确解密密钥的人才能访问其真实内容。加密技术在现代社会中被广泛应用于各种场景,包括但不…...
编程-设计模式 22:策略模式
设计模式 22:策略模式 定义与目的 定义:策略模式定义了一系列算法,并将每一个算法封装起来,使它们可以互相替换。策略模式让算法的变化独立于使用算法的客户。目的:该模式的主要目的是将一组相关的算法封装成一系列可…...
kafka 将log4j的项目升级到log4j2
kafka版本是kafka_2.11-2.0.0,由于引用的log4j有漏洞,而升级kafka可能影响比较大,所以更新log4j包的版本。 参考的是将log4j的项目升级到log4j2 主要步骤如下: cd kafka的目录 cd libs rm -f slf4j-log4j12-1.7.25.jar rm -f …...
【CSP2019 模拟赛】Time
题目描述: 小 A 现在有一个长度为 𝑛 的序列 {𝑥𝑖},但是小 A 认为这个序列不够优美。 小 A 认为一个序列是优美的,当且仅当存在 𝑘 ∈ [1, 𝑛],满足: &#…...
二叉树相关的算法题
二叉树相关的算法题 单值二叉树 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时,才返回 true;否则返回 false。 示例 1: 输入:[1,1,1,1,1,null,1] 输出:t…...
Unity URP 曲面细分学习笔记
学百人时遇到了曲面着色器的内容,有点糊里糊涂,于是上知乎找到了两篇大佬的文章 Unity URP 曲面细分 和 Unity曲面细分笔记,本文只是自己做学习记录使用 1.曲面细分与镶嵌 曲面细分或细分曲面(Subdivision surface)是…...
每天五分钟深度学习pytorch:训练神经网络模型的基本步骤
本文重点 本文个人认为是本专栏最重要的章节内容之一,前面我们学习了pytorch中的基本数据tensor,后面我们就将学学习深度学习模型的内容了,在学习之前,我们先来看一下我们使用pytorch框架训练神经网络模型的基本步骤,然后我们下面就将这些步骤分解开来,详细学习。 代码…...
【langchain学习】使用缓存优化langchain中的LLM调用性能:内存、SQLite与Redis的对比
在处理语言模型(LLM)调用时,特别是在需要多次执行相同请求的情况下,缓存机制能够显著提升系统的性能。本文通过对比内存缓存(InMemoryCache)、SQLite缓存(SQLiteCache)和Redis缓存(RedisCache),探讨了如何在Langchain中使用这些缓存机制来优化LLM调用的性能。 代码…...
spring boot 集成EasyExcel
EasyExcel 是一个基于 Java 的快速、简洁的 Excel 处理工具,它能够在不用考虑性能和内存等因素的情况下,快速完成 Excel 的读写功能。 首先,需要在 Spring Boot 项目中引入 EasyExcel 依赖。在 pom.xml 文件中添加以下依赖: <d…...
获取对象中第一个存在的值
在JavaScript中,要从一个对象中获取第一个存在的(非undefined、非null、非空数组等)值,你可以使用Object.values()方法结合Array.prototype.find()方法。以下是一个示例代码,演示如何实现这一点: const ob…...
Python学习笔记----集合与字典
1. 字符串、列表和元组的元素都是按下标顺序排列,可通过下 标直接访问,这样的数据类型统称为序列。 其中,字符串和元组中的元素不能修改,而列表中的元素可以修改。 集合 1. 与元组和列表类似,Set (集合&a…...
c# 排序、强转枚举
List<Tuple<double,int>> mm中doble从小到大排序 mm本身排序 在C#中,如果你有一个List<Tuple<double, int>>类型的集合mm,并且你想要根据Tuple中的double值(即第一个元素)从小到大进行排序,同…...
“华为杯”第十六届中国研究生数学建模竞赛-C题:视觉情报信息分析
目录 摘 要: 一、问题重述 二、模型假设 三、符号说明 四、问题一分析与求解 4.1 问题一分析 4.2 模型建立 4.2.1 位置变换模型建立 4.2.4 多平面转换模型建立 4.3 模型求解 4.3.1 问题一图 1 结果 4.3.2 问题一图 2 结果 4.3.3 问题一图 3 结果 4.3.4 问题一图 4 结果 4.4 模…...
html+css+js网页设计 找法网2个页面(带js)ui还原度百分之90
htmlcssjs网页设计 找法网2个页面(带js)ui还原度百分之90 网页作品代码简单,可使用任意HTML编辑软件(如:Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑…...
018 | backtrader回测反转策略
什么是反转策略? 反转策略(Reversal Strategy)是一种试图捕捉市场价格趋势逆转的交易策略。与趋势跟随策略不同,反转策略的核心理念是“物极必反”,即价格在经过一段时间的单边趋势后,往往会出现逆转的机会…...
《图解HTTP》全篇目录
前言 目前,国内讲解 HTTP 协议的书实在太少了。在我的印象中,讲解网络协议的书仅有两本。一本是《HTTP 权威指南》,但其厚度令人望而生畏;另一本是《TCP/IP 详解,卷 1》,内容艰涩难懂,学习难度…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
