2024第十五届蓝桥杯C++大学A组压轴题解:封印宝石

2024-05-15 16:52

本文主要是介绍2024第十五届蓝桥杯C++大学A组压轴题解:封印宝石,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:第十五届蓝桥杯C++大学A组省赛压轴题

题目传送门

题意:将n个数放在n个位置上,每个数只能放在它自己之前的位置上,且离自己多远就花费多少代价,可以有没放的数,给出最大代价要求最后放的数排成的字典序最大。

字典序最大带来的就必定是贪心,必须每次都把能放最大的一个值放到前面,同时为了节省体力,需要选相同的这个最大值最前面的一个。

对于当前位置i,也就是求i到i+k(当前体力)最大且最靠前的一个数,可以用线段树。同时,题目要求不能连续放一样的数,也就是说最大值有时候放不进去,我们需要放严格次大值,因此同时维护严格次大值,线段树可以实现。最后,在每次放入后要把放入的删掉。

tip:这道题的修改和维护其实挺简单的,但是注意两点

1:注意次大值的一些特殊情况

2:别忘了位置要最靠前

AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005],ans[1000005];
bool f[1000005];
struct node
{int id,val;node(){val=id=0;}
}Zero;
bool operator<(node x,node y)
{if(x.val==y.val)return x.id>y.id;return x.val<y.val;
}y
bool operator==(node x,node y)
{return x.val==y.val;
}
struct Tree
{int l,r;node mx1,mx2;Tree(){mx1.val=mx1.id=0,mx2.val=mx2.id=0;}
}t[1000005];
node a1[4];
inline void Pushup(int i)
{a1[0]=t[i*2].mx1,a1[1]=t[i*2].mx2,a1[2]=t[i*2+1].mx1,a1[3]=t[i*2+1].mx2;sort(a1,a1+4);t[i].mx1=a1[3];for(int j=2;j>=0;j--)if(a1[j].val!=a1[j+1].val){t[i].mx2=a1[j];break;}
}
inline void Build(int i,int l,int r)
{if(l==r){t[i].mx1.val=a[l],t[i].mx1.id=l,t[i].l=l,t[i].r=r;return;}int mid=(l+r)/2;Build(i*2,l,mid);Build(i*2+1,mid+1,r);Pushup(i);
}
node m1,m2;
inline node Max1(int i,int l,int r,int l1,int r1)
{if(l1<=l&&r1>=r){a1[0]=t[i].mx1,a1[1]=t[i].mx2,a1[2]=m1,a1[3]=m2;sort(a1,a1+4);m1=a1[3];for(int j=2;j>=0;j--)if(a1[j].val!=a1[j+1].val){m2=a1[j];break;}return t[i].mx1;}if(l1>r||r1<l)return Zero;int mid=(l+r)/2;return max(Max1(i*2,l,mid,l1,r1),Max1(i*2+1,mid+1,r,l1,r1));
}
inline void Modify(int i,int l,int r,int x1)
{if(l>x1||r<x1)return;if(l==x1&&r==x1){t[i].mx1=t[i].mx2=Zero;return;}int mid=(l+r)/2;Modify(i*2,l,mid,x1);Modify(i*2+1,mid+1,r,x1);Pushup(i);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);Build(1,1,n);for(int i=1;i<=n;i++){m1=m2=Zero;Max1(1,1,n,i,min(i+m,n));if(m1.val==ans[i-1]){if(m2.val){ans[i]=m2.val;Modify(1,1,n,m2.id);m-=m2.id-i;}}if(m1.val!=ans[i-1]&&m1.val){ans[i]=m1.val;Modify(1,1,n,m1.id);m-=m1.id-i;}}for(int i=1;i<=n;i++)printf("%d ",ans[i]?ans[i]:-1);return 0;
}

这篇关于2024第十五届蓝桥杯C++大学A组压轴题解:封印宝石的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/992388

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能