【算法每日一练】

蛮有意思的的一道题,最后要判断能否成为一种1~n的全排列,我最这样做的:

整个数组先排序一下。假设遍历到了i,那就判断前面b和r的个数,但是有想到了后面可能还会对前面的结果产生影响,所以就抛弃了这个想法。

然后就想:既然是一种排序,那么能不能先把这个排序确定下来呢,事实上是可以的。

做法就成了这样子:整个数组还是先排序,降序排序,然后把r放在b前面。(一会解释)

假如说现在变成了这样:

6 4 4 3 3 1(r r b r b r)

那么6可以变成6,4也可以变成5,4也可以变成4,3也可以变成3,3也可以变成2,1也可以变成1

这样就变成了6 5 4 3 2 1

但是我实际是升序来写的,因为更方便一点,还有一点就是要注意有时候可能光升序并不能判断出所有情况,还要降序再来一次,所以我reverse了一下。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
	int x;char c;
}a[N];
int t,n;
bool cmp(node a,node b){
	if(a.x!=b.x)return a.x<b.x;
	else return a.c<b.c;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;string s;
		for(int i=1;i<=n;i++)cin>>a[i].x;
		cin>>s;
		for(int i=1;i<=n;i++)a[i].c=s[i-1];
		sort(a+1,a+n+1,cmp);
		int f1=0;
		for(int i=1;i<=n;i++){
			if(a[i].x==i)continue;
			else if(a[i].x<i&&a[i].c=='R')continue;
			else if(a[i].x>i&&a[i].c=='B')continue;
			else {f1=1;break;}
		}
		reverse(a+1,a+1+n);
		int f2=0;
		for(int i=1;i<=n;i++){
			if(a[i].x==i)continue;
			else if(a[i].x<i&&a[i].c=='R')continue;
			else if(a[i].x>i&&a[i].c=='B')continue;
			else {f2=1;break;}
		}
		if(f1==0||f2==0)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

        

        

这个题肯定是要排序的(根据直觉),那么最好是按照人数要求来降序排序,这样的话遍历到当前的人的要求时候,就不需要再考虑前面的那么人了。

所以我们先排序,然后一次遍历每个人,如果当前的人数要求满足就直接放进来,如果不满足就看情况来踢掉当前队伍中战力最低的人。所以我们还需要一个优先级队列优化。

还有一点需要注意:

在队伍放入两个人后:总战力是60,人数是2

再遍历第三个人的时候,发现人数过多,那么就应该踢掉一个人,此人战力20小于120,所以这个人就踢掉,然后还需要踢一个人,比较此人的战力40小于120,所以也踢掉。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node{
	ll A,B;
//	bool operator>(const node &b)const {return A>b.A;}
}a[N];
bool operator>(const node &a,const node &b){
	return a.A>b.A;
}
ll ans,n,sum;
priority_queue<node,vector<node>,greater<node> >q;
bool cmp(node a,node b){
	return a.B>b.B;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].A>>a[i].B;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		q.push(a[i]);
		sum+=a[i].A;
		while(q.size()>a[i].B){
			sum-=q.top().A;
			q.pop();
		}
		ans=max(ans,sum);
	}
	cout<<ans;
	return 0;

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/584641.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Now in Android 4月份更新速览

Now in Android 4月份更新速览 1. 引言 Android 15 Beta的发布标志着Android生态系统的新一轮更新。这次更新旨在提升用户体验和开发效率&#xff0c;让我们一起来了解其中的重要内容。 2. Android 15 Beta介绍 Android 15 Beta带来了一系列新功能&#xff0c;其中包括默认边…

JAVA同城服务美容美发到店服务上门服务系统源码微信小程序+微信公众号+H5+APP

随着科技的飞速发展&#xff0c;互联网和移动互联网已经渗透到我们生活的方方面面&#xff0c;同城服务美容美发到店服务上门服务系统应运而生&#xff0c;为整个行业带来了巨大的变革和无限的可能。该系统的重要性和优势不言而喻&#xff0c;对于行业发展和用户需求的影响深远…

文件系统学习

软连接&#xff1a;可以跨不同的磁盘块&#xff0c;创建出不同的inode节点 应连接&#xff1a;相同的inode节点&#xff0c;不同的文件名字记录在父亲节点目录中 分区(fdisk)&#xff0c;格式化(mkfs)&#xff0c;挂载(mount)&#xff0c;大于2T分区&#xff08;parted&#…

Go常用的标准库——fmt,time

一.fmt fmt包实现了类似C语言printf和scanf的格式化I/O。主要分为向外输出内容和获取输入内容两大部分。 1.1 向外输出 标准库fmt提供了以下几种输出相关函数。 Print Print系列函数会将内容输出到系统的标准输出&#xff0c;区别在于Print函数直接输出内容&#xff0c;没有换…

【数据结构】二叉树-堆

一、树概念及结构 1.1树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限节点组成的一个具有层次的关系的集合。 注意&#xff1a;子树不能相交 节点的度&#xff1a;一个节点含有的子树个数称为该节点的度&#xff1b;A为6&#x…

Elasticsearch 索引的分片和副本是什么意思,如何扩展分片

文章目录 前言Elasticsearch 索引的分片和副本是什么意思&#xff0c;如何扩展分片示例:1. 设置 5个分片&#xff0c;每个分片一个副本的命令2. 将5个分片扩展到10个分片 前言 如果您觉得有用的话&#xff0c;记得给博主点个赞&#xff0c;评论&#xff0c;收藏一键三连啊&…

LabVIEW航空发动机主轴承试验器数据采集与监测

LabVIEW航空发动机主轴承试验器数据采集与监测 随着航空技术的迅速发展&#xff0c;对航空发动机性能的测试与监测提出了更高的要求。传统的数据采集与监测方法已难以满足当前高精度和高可靠性的需求&#xff0c;特别是在主轴承试验方面。基于LabVIEW的航空发动机主轴承试验器…

Linux|awk 特殊模式“BEGIN 和 END”

引言 在本文[1]&#xff0c;我们将介绍Awk的更多特性&#xff0c;特别是两个特殊的模式&#xff1a;BEGIN和END。 这些独特的功能在我们努力扩展和深入探索构建复杂Awk操作的多种方法时&#xff0c;将大有裨益。 实例 让我们从Awk系列的开篇回顾开始&#xff0c;回想一下&#…

指纹浏览器:网络安全与隐私的新工具

在互联网时代&#xff0c;隐私和网络安全成为人们越来越关注的话题。随着数字化的发展&#xff0c;个人信息的泄露和在线追踪的问题愈发严峻。在这个背景下&#xff0c;"指纹浏览器"作为一种新型工具&#xff0c;开始受到关注。撸空投需要了解指纹浏览器。本文将深入…

【启明智显技术分享】关于RS485自动收发电路的问题整理

*【编者按】*随着信息技术的飞速发展&#xff0c;芯片作为现代电子设备的核心组成部分&#xff0c;其应用领域的拓展与性能的提升都成为了业界关注的焦点。在芯片应用过程中&#xff0c;各位小伙伴可能会遇到各种各样的问题。“RS485自动收发电路”作为芯片应用中的一项关键技术…

Prometheus+Grafana多方位监控

PrometheusGrafana多方位监控 契机 ⚙ 最近发现火山引擎有托管的Prometheus,可是当前是邀测阶段。并且发现火山云的ECS是自带开机自启的exporter的。刚好需要搭建一套服务器监控&#xff0c;所以研究了一套Prometheus监控&#xff0c;包含linux主机监控nginx监控es监控rabbitM…

Python俄罗斯方块

文章目录 游戏实现思路1. 游戏元素的定义2. 游戏区域和状态的定义3. 游戏逻辑的实现4. 游戏界面的绘制5. 游戏事件的处理6. 游戏循环7. 完整实现代码 游戏实现思路 这个游戏的实现思路主要分为以下几个步骤&#xff1a; 1. 游戏元素的定义 Brick类&#xff1a;表示游戏中的砖…

CSS样式特异性5层次详解

你好&#xff0c;我是云桃桃。 一个希望帮助更多朋友快速入门 WEB 前端的程序媛。 云桃桃-大专生&#xff0c;一枚程序媛&#xff0c;感谢关注。回复 “前端基础题”&#xff0c;可免费获得前端基础 100 题汇总&#xff0c;回复 “前端工具”&#xff0c;可获取 Web 开发工具合…

云端芳华、运维之美

今天&#xff0c;在我们享受互联网服务带来的便利与高效的同时&#xff0c;有一群人默默地在幕后为我们提供支持&#xff0c;他们就是云端运维人员。 值此五一国际劳动节来临之际&#xff0c;我们要真诚感谢他们辛勤的劳动和奉献&#xff01;

基于ssm+vue开放式教学评价管理系统【ppt·代码·文档报告】

项目演示视频 项目名称&#xff1a;开放式教学评价管理系统 系统介绍&#xff1a;本系统是通过java的SSM框架来实现的&#xff0c;前端采用vue框架进行实现 管理员通过登录进入到系统操作界面&#xff0c;结合需求可以对个人信息进行在线修改维护&#xff0c;也可结合需求进行…

经典文献阅读之--SurroundOcc(自动驾驶的环视三维占据栅格预测)

0. 简介 环视BEV已经是很多场景中需要的功能&#xff0c;也是视觉代替激光雷达的有效解决方案&#xff0c;而《SurroundOcc: Multi-camera 3D Occupancy Prediction for Autonomous Driving》一吻则代表了这个领域的SOTA算法&#xff0c;文中通过多帧点云构建了稠密占据栅格数据…

【设计模式】抽象工厂模式(Abstract Factory Pattern)

目录标题 抽象工厂设计模式详解1. 介绍2. 结构3. 实现步骤3.1 创建抽象产品接口3.2 创建具体产品类3.3 创建抽象工厂接口3.4 创建具体工厂类 4. 好处与优点5. 坏处与缺点6. 适用场景7. 总结 抽象工厂设计模式详解 1. 介绍 抽象工厂模式是一种创建型设计模式&#xff0c;它提供…

Kimichat使用技巧:方便又实用的kimi+智能体

今天kimi智能助手推出了kimi的功能。简单的说&#xff0c;就是一系列kimi已经写好的提示词&#xff0c;用户可以直接调用、对话。 Kimi分为官方推荐、办公提效、辅助写作、社交娱乐、生活实用这几类。可以从左边侧边栏点击进入。 官方推荐的有&#xff1a; Kimi 001号小客服&…

c语言——二叉树

目录 目录 二叉树关键概念理解 一颗拥有1000个结点的树度为4&#xff0c;则它的最小深度是&#xff1f; 那么对于二叉树&#xff0c;只掌握这些是远远不够的&#xff0c;我们还需要掌握几个最基本的经典问题&#xff0c; 求二叉树大小 求叶子结点个数 求深度 求第k层的…

多线程编程9——线程池

一、为什么要引入线程池&#xff1f; 虽然对比进程&#xff0c;线程已经很轻量了&#xff0c;创建销毁调度线程都更高效。但是随着并发程度的提高&#xff0c;我们对于性能要求的标准也越来越高&#xff0c;当我们需要频繁创建销毁调度线程时&#xff0c;就发现线程也没有那么…