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》,内容艰涩难懂,学习难度…...
如何轻松备份微信聊天记录:WeChatMsg完整指南让数据掌控权回归你手
如何轻松备份微信聊天记录:WeChatMsg完整指南让数据掌控权回归你手 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trend…...
保姆级教程:用SolidWorks URDF插件把你的机械设计变成Gazebo仿真模型
从SolidWorks到Gazebo:机械设计仿真全流程实战指南 机械工程师们常常面临一个挑战:如何在虚拟环境中快速验证设计方案的可行性?SolidWorks作为主流的三维设计工具,与Gazebo这一强大的机器人仿真平台结合,能够实现从概念…...
AirPods Pro 3 与 Bose QC Ultra Earbuds 2:无线耳机市场的激烈较量
AirPods Pro 3 与 Bose QC Ultra Earbuds 2:新功能大比拼最新款的 AirPods Pro 3 引入了一系列新功能,提升了音频效果,增强了降噪能力,还具备助听模式、实时翻译、自动切换、空间音频、心率监测等附加功能。而 Bose QuietComfort …...
S32K3项目中途想换调试器?手把手教你为已有工程添加Lauterbach调试接口
S32K3项目中途切换调试器:无缝迁移Lauterbach接口的工程实践 在嵌入式开发领域,调试工具的灵活切换往往意味着效率的飞跃。想象这样一个场景:你正在使用NXP S32K3系列MCU开发汽车电子控制单元,项目已进行到中期测试阶段࿰…...
告别内存映射:用AXI-Stream协议搞定FPGA视频流传输(附时序图解析)
告别内存映射:用AXI-Stream协议搞定FPGA视频流传输(附时序图解析) 在FPGA视频处理系统中,数据流的传输效率往往成为性能瓶颈。传统的内存映射方式虽然通用,但对于高吞吐量的视频数据流却显得力不从心。AXI-Stream协议以…...
学习神经网络
一、神经网络概述:人工智能的核心基石(一)神经网络的定义与起源神经网络,全称为人工神经网络(Artificial Neural Network,ANN),是一种模仿生物神经网络(动物大脑神经元网…...
基于Dify的智能问答系统:从意图识别到规范化回复的全流程设计
1. 从零开始理解Dify智能问答系统 第一次接触Dify时,我完全被它的可视化编排能力惊艳到了。这个平台就像搭积木一样,让不懂代码的产品经理也能设计出复杂的AI应用。举个实际例子,去年我们团队要做一个游泳健身领域的问答助手,传统…...
浏览器资源嗅探终极指南:如何轻松下载网页视频与音频
浏览器资源嗅探终极指南:如何轻松下载网页视频与音频 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 你是否曾想保存网页上的精彩视频却…...
YOLOv12性能优化 | 注意力融合 | 实战解析CBAM模块的集成与调优
1. CBAM注意力机制的核心原理与实战价值 第一次接触CBAM模块时,我被它简洁高效的设计惊艳到了。这个由通道注意力和空间注意力组成的双剑客,能在不显著增加计算量的情况下,让模型学会"该看哪里"。想象一下教小朋友看图说话…...
Postman实战指南:深入解析CORS预检请求与响应头配置
1. 为什么CORS会成为开发者的噩梦? 第一次遇到CORS问题时,我盯着浏览器控制台那个鲜红的报错信息整整发呆了十分钟。"Access-Control-Allow-Origin"这个看起来人畜无害的响应头,竟然能让整个前端应用瘫痪。后来才发现,这…...
