蓝桥杯倒计时 43天 - 前缀和



思路:如果用n^2复杂度暴力会超时。nlogn 可以,利用前缀和化简,提前存储某个位置前的每个石头搬运到该位置和每个石头后搬运到该位置的前缀和On最后直接输出 On。排序花 nlogn
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define w second
#define p first
const int N = 1e5+10;
typedef long long LL;
PII q[N];
int n;
LL pre[N],nex[N];int main( ){cin>>n;for(int i=1;i<=n;i++){cin>>q[i].w>>q[i].p;}sort(q+1,q+1+n);LL s = 0;for(int i=2;i<=n;i++){s+=q[i-1].w;pre[i] = (q[i].p-q[i-1].p)*s+pre[i-1];}s = 0;for(int i=n-1;i>=1;i--){s+=q[i+1].w;nex[i] = (q[i+1].p-q[i].p)*s+nex[i+1];}LL ans = 1e18;pre[0]=0;nex[n]=0;for (int i = 1; i <= n; ++ i )ans = min(ans, pre[i] + nex[i]);cout<<ans<<'\n';return 0;
}相关文章:
蓝桥杯倒计时 43天 - 前缀和
思路:如果用n^2复杂度暴力会超时。nlogn 可以,利用前缀和化简,提前存储某个位置前的每个石头搬运到该位置和每个石头后搬运到该位置的前缀和On最后直接输出 On。排序花 nlogn #include<bits/stdc.h> using namespace std; typedef pai…...
【Web - 框架 - Vue】随笔 - Vue的简单使用(01) - 快速上手
【Web - 框架 - Vue】随笔 - Vue的简单使用(01) - 快速上手 Vue模板代码 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>模板</title> </head> <body> <div></di…...
【简说八股】Redisson的守护线程是怎么实现的
Redisson Redisson 是一个 Java 语言实现的 Redis SDK 客户端,在使用分布式锁时,它就采用了「自动续期」的方案来避免锁过期,这个守护线程我们一般也把它叫做「看门狗」线程。 Redission是一个在Java环境中使用的开源的分布式缓存和分布式锁实…...
WPS/Office 好用的Word插件-查找替换
例如:一片文档:…………泰山…………泰(少打了山字)………… 要是把“泰”查找替换为“泰山”,就会把前面的“泰山”变成“泰山山”,这种问题除了再把“泰山山”查找替换为“泰山”,有没有更简单…...
Go 简单设计和实现可扩展、高性能的泛型本地缓存
相信大家对于缓存这个词都不陌生,但凡追求高性能的业务场景,一般都会使用缓存,它可以提高数据的检索速度,减少数据库的压力。缓存大体分为两类:本地缓存和分布式缓存(如 Redis)。本地缓存适用于…...
Vue.js 深度解析:模板编译原理与过程
🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 E…...
Java多线程——如何保证原子性
目录 引出原子性保障原子性CAS 创建线程有几种方式?方式1:继承Thread创建线程方式2:通过Runnable方式3:通过Callable创建线程方式4:通过线程池概述ThreadPoolExecutor API代码实现源码分析工作原理:线程池的…...
stm32消息和邮箱使用
邮箱管里介绍 邮箱是C/OS-II中另一种通讯机制,它可以使一个任务或者中断服务子程序向另一个任务发送一个指针型的变量。该指针指向一个包含了特定“消息”的数据结构。为了在C/OS-II中使用邮箱,必须将OS_CFG.H中的OS_MBOX_EN常数置为1。使用邮箱之前,必须先建立该邮箱。该操…...
银行数字化转型导师坚鹏:银行数字化转型案例研究
银行数字化转型案例研究 课程背景: 数字化背景下,很多银行存在以下问题: 不清楚银行科技金融数智化案例? 不清楚银行供应链金融数智化案例? 不清楚银行普惠金融数智化案例? 不清楚银行跨境金融数智…...
142.乐理基础-音程的构唱练习
内容参考于:三分钟音乐社 上一个内容:141.乐理基础-男声女声音域、模唱、记谱与实际音高等若干问题说明-CSDN博客 本次内容最好去看视频: https://apphq3npvwg1926.h5.xiaoeknow.com/p/course/column/p_5fdc7b16e4b0231ba88d94f4?l_progra…...
【比较mybatis、lazy、sqltoy、mybatis-flex操作数据】操作批量新增、分页查询(二)
orm框架使用性能比较 环境: idea jdk17 spring boot 3.0.7 mysql 8.0比较mybatis、lazy、sqltoy、mybatis-flex操作数据 测试条件常规对象 orm 框架是否支持xml是否支持 Lambda对比版本mybatis☑️☑️3.5.4sqltoy☑️☑️5.2.98lazy✖️☑️1.2.4-JDK17-SNAPS…...
每日OJ题_链表②_力扣24. 两两交换链表中的节点
目录 力扣24. 两两交换链表中的节点 解析代码 力扣24. 两两交换链表中的节点 24. 两两交换链表中的节点 难度 中等 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即&…...
C语言数据类型详解及相关题——各种奇奇怪怪的偏难怪
文章目录 一、C语言基本数据类型溢出 二、存储原理符号位原码反码补码补码操作的例子 三、赋值中的类型转换常见返回类型——巨坑总结 一、C语言基本数据类型 溢出 因为数据范围(即存储单元的位的数量)的限制,可以表达的位数是有限的。 溢出…...
经典语义分割(二)医学图像分割模型UNet
经典语义分割(二)医学图像分割模型UNet 我们之前介绍了全卷积神经网络( FCN) ,FCN是基于深度学习的语义分割算法的开山之作。 今天我们介绍另一个语义分割的经典模型—UNet,它兼具轻量化与高性能,通常作为语义分割任务的基线测试模型&#x…...
三天学会阿里分布式事务框架Seata-seata事务日志mysql持久化配置
锋哥原创的分布式事务框架Seata视频教程: 实战阿里分布式事务框架Seata视频教程(无废话,通俗易懂版)_哔哩哔哩_bilibili实战阿里分布式事务框架Seata视频教程(无废话,通俗易懂版)共计10条视频&…...
C语言-简单实现单片机中的malloc示例
概述 在实际项目中,有些单片机资源紧缺,需要mallloc内存,库又没有自带malloc函数时,此时,就需要手动编写,在此做个笔录。(已在项目上使用),还可进入对齐管理机制。 直接…...
外包干了2年,技术退步明显
先说一下自己的情况,研究生,19年进入广州某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...
计算机网络面经-HTTPS加密过程
前言 在上篇文章HTTPS详解一中,我已经为大家介绍了 HTTPS 的详细原理和通信流程,但总感觉少了点什么,应该是少了对安全层的针对性介绍,那么这篇文章就算是对HTTPS 详解一的补充吧。还记得这张图吧。 HTTPS 和 HTTP的区别 显然&am…...
2024年最佳硬盘!为台式电脑、NAS等产品量身定做的顶级机械硬盘
机械硬盘(HDD)可能看起来像是古老的技术,但它们仍然在许多地方提供“足够好”的性能,并且它们很容易以同等的价格提供最多的存储空间。 尽管最好的SSD将为你的操作系统和引导驱动器提供最好的体验,并提供比HDD更好的应…...
串的匹配算法——BF算法(朴素查找算法)
串的模式匹配:在主串str的pos位置查找子串sub,找到返回下标,没有找到返回-1。 1.BF算法思想 相等则继续比较,不相等则回退;回退是i退到刚才位置的下一个(i-j1);j退到0;利用子串是否…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...
