AcWing4655.重新排序

【题目链接】4655. 重新排序 - AcWing题库

输入样例:
5
1 2 3 4 5
2
1 3
2 5
输出样例:
4

【代码及详细注释】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N],b[N],s[N];
//a用于存储原本的数组
//b用于差分 
//s用于存储前缀和求出最开始的和
//贪心思想:让出现次数多的区间点分配到最大的数 
int n,m;
void add(int l,int r)
{
	b[l]+=1;
	b[r+1]-=1;
}
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	cin>>m;
	ll ans=0,res=0;//ans用于存储原本的计算结果,res用于计算重新排列后的结果
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		ans+=s[r]-s[l-1];
		add(l,r);//l-r区间上每个数都要出现一次 
	 } 
	for(int i=1;i<=n;i++)
		b[i]+=b[i-1];
	sort(b+1,b+1+n,cmp);
	sort(a+1,a+1+n,cmp);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0) break;
		res+=a[i]*b[i];
	}
	cout<<res-ans;
	return 0;
 } 
 

 

 

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

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

相关文章

国税发票查验接口、电子增值税发票查验接口、数电票查验接口

翔云发票查验接口支持增值税发票管理系统开具发票的真伪&#xff0c;通过发票代码、号码、日期、金额、校验码四要素信息进行真伪的查验&#xff0c;支持返回全票面信息&#xff0c;API接口便于集成&#xff0c;可适用于多种应用场景。 发票查验接口python调用示例&#xff1a;…

MYSQL原理学习篇简记(二)

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是小周同志&#xff0c;25届双非校招生Java选手&#xff0c;很高兴认识大家 &#x1f4d5;学习出处&#xff1a;本文是学自小林coding (xiaolincoding.com) 网站的MYSQL图解篇 &#x1f525;如果感觉博主的文章还不错的…

在IIS中启用动态压缩

在iis管理中 对网站启用压缩可以节省带宽 提高网站的响应速度&#xff0c;默认情况下IIS启用多了“静态内容”的压缩。 下面就如何启用“动态内容压缩”说说方法&#xff1a; 1.打开iis中的网站&#xff0c;右侧管理项中显示有压缩 2、双击打开“压缩”&#xff0c;“静态内容…

cocos creator 实现spine局部换装

1 使用3.7.4版本 2 js代码 3 c Native层修改源码

太阳光光照试验耐久性老化试验使用太阳光模拟器系统

上海科迎法电气科技有限公司生产的太阳光模拟器系统主要应用于太阳能研究、材料研究、光伏组件测试、空间环境模拟器、植物生长研究、光热模拟等领域&#xff0c;主要表现特征为&#xff1a; 1. 太阳能研究&#xff1a;可用于模拟不同光照条件下太阳能电池的性能测试和研究&am…

学习python你必须弄懂的 Python、Pycharm、Anaconda 三者之间的关系

省流版 Python作为深度学习和人工智能学习的热门语言&#xff0c;学习一门语言&#xff0c;除了学会其简单的语法之外还需要对其进行运行和实现&#xff0c;才能实现和发挥其功能和作用。下面来介绍运行Python代码常用到的工具总结。 文中部分内容来自GPT&#xff0c;他已经是…

Quantum Temple借助Sui通过NFT推动再生旅游

从金融到艺术&#xff0c;从游戏到无线网络&#xff0c;各行各业都涌现出大量初创公司&#xff0c;利用区块链技术颠覆现状。说到旅游业&#xff0c;让人联想到拥挤的机场、快节奏的旅游和豪华游轮&#xff0c;可能看起来对区块链创新持守旧态度。一家初创公司认为现在是时候改…

ELK 日志分析系统(一)

一、概念 二、详解 2.1 Elasticsearch 核心概念 2.1.1 接近实时(NRT) 2.1.2 cluster集群 2.1.3 Node节点 2.1.4 index索引 2.1.5 类型&#xff08;type&#xff09; 2.1.6 文档&#xff08;document) 2.1.7 分片和副本(shards & replicas) 2.2 Logstash主要组件 …

Navicat Premium 16 for Mac/Win:数据库管理的全能之选

在数字化时代&#xff0c;数据库管理已成为各行各业不可或缺的一环。而Navicat Premium 16作为一款功能强大的数据库管理软件&#xff0c;无疑为数据库管理员和开发者提供了高效、便捷的解决方案。 Navicat Premium 16支持多种主流数据库系统&#xff0c;无论是MySQL、Postgre…

【蓝桥杯】2024年第15届真题题目

试题 A: 握手问题 本题总分&#xff1a; 5 分 【问题描述】 小蓝组织了一场算法交流会议&#xff0c;总共有 50 人参加了本次会议。在会议上&#xff0c; 大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进 行一次握手&#xff08;且仅有一次&a…

初识SpringMVC(SpringMVC学习笔记一)

1 、还是熟悉的配方&#xff0c;先创建一个父Maven项目&#xff08;忘记怎么创建项目了就去前面翻笔记&#xff09;&#xff0c;导入通用的配置依赖 <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instan…

基于Java社团管理系统设计与实现(源码+部署文档)

博主介绍&#xff1a; ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ &#x1f345; 文末获取源码联系 &#x1f345; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅 &#x1f447;&#x1f3fb; 不然下次找不到 Java项目精品实…

【pycharm】运行完程序之后如何查看变量情况

【pycharm】运行完程序之后如何查看变量情况 Matlab运行完代码可以在工作区查看变量以及变量值&#xff0c;对于python也是可以的 pycharm运行完程序之后如何查看变量情况方法&#xff1a;选择edit configurations 把run with python console勾上 然后运行完代码就可以在下面查…

水离子雾化壁炉与酒店会客厅的氛围搭配

水离子雾化壁炉与酒店会客厅的氛围搭配可以营造出舒适、温馨和现代化的氛围&#xff0c;以下是一些建议&#xff1a; 焦点装饰&#xff1a;将水离子雾化壁炉设计成会客厅的焦点装饰物&#xff0c;使其成为客人进入会客厅后第一眼的吸引点。选择设计独特、现代化的壁炉造型&…

微信公众号迁移申请函怎么填写?

公众号迁移的好处有哪些&#xff1f;迁移后原公众号还能用吗&#xff1f;公众号迁移的好处有很多哦&#xff01;比如可以获得更多权限功能、公司变更或注销时可以保证账号的正常使用、收购账号后可以改变归属权或使用权等等。不过要注意的是&#xff0c;迁移后原公众号就不能再…

量化过程信息损耗分析(MATLAB)

MATLAB代码 clear_all; Mrand(5,5)*100;% 假设M是待转换的矩阵 a min(M(:)); b max(M(:));% 将M映射到[0, 255] M_mapped functionA(M, a, b); M_mapped_floorfloor(M_mapped); % 将M_mapped恢复到原始范围 M_original functionB(M_mapped_floor, a, b);disp(M); disp(M_m…

DNF手游攻略:2024新手攻略大全

在《DNF手游》的世界中&#xff0c;前期阶段对于新手玩家来说至关重要。以下是一份综合整理的新手攻略&#xff0c;帮助玩家快速适应游戏并取得进展。 1. 角色建立策略&#xff1a; 在前期&#xff0c;建议玩家建立3个角色&#xff0c;包括1个大号和2个小号。大号可以根据个人喜…

Hystrix应用:如何在Spring Boot中使用Hystrix?

Hystrix应用&#xff1a;如何在Spring Boot中使用Hystrix&#xff1f; 引言 在微服务架构的发展过程中&#xff0c;面对复杂的服务依赖和不可预见的系统故障&#xff0c;如何提升系统的容错能力成为了一个非常急迫且重要的能力。 由 Netflix&#xff08;网飞&#xff09;公司…

佛山分公司迎来重要指导蒋书记一行及杭州区域分公司领导共襄盛举

近日&#xff0c;佛山分公司迎来了一场重要的指导活动。蒋书记携夫人&#xff0c;以及助理黄显文和公司工作人员施晓燕等一行领导莅临佛山分公司&#xff0c;为公司的未来发展提供了宝贵的指导意见。同时&#xff0c;江浙福地区的杭州区域分公司负责人白棋元总和朱建江总也亲临…

Java 基于微信小程序的智能停车场管理小程序

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…