当前位置: 首页 > news >正文

CF1574C Slay the Dragon 题解

CF1574C Slay the Dragon 题解

  • 题目
    • 链接
    • 字面描述
      • 题面翻译
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
        • 样例输入 #1
        • 样例输出 #1
      • 提示
  • 代码实现

题目

链接

https://www.luogu.com.cn/problem/CF1574C

字面描述

题面翻译

给定长度为 nnn 的序列 aaammm 次询问,每次询问包含两个参数 x,yx,yx,y,你可以给序列任意位置 +1+1+1,最后你需要找出一个位置 ppp ,满足

  • ap≥xa_p\ge xapx
  • ∑i=1nai[i≠p]≥y\displaystyle\sum_{i=1}^n a_i[i\not= p] \ge yi=1nai[i=p]y

最小化 +1+1+1 次数,输出其次数。

限制2≤n≤2×105,1≤m≤2×105,1≤ai,x≤1012,1≤y≤10182\le n\le2\times 10^5,1\le m\le 2\times10^5,1\le a_i,x\le 10^{12},1\le y\le 10^{18}2n2×105,1m2×105,1ai,x1012,1y1018

Translated by 飞丞

题目描述

Recently, Petya learned about a new game “Slay the Dragon”. As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of $ n $ heroes, the strength of the $ i $ -th hero is equal to $ a_i $ .

According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon’s defense is equal to $ x $ , then you have to send a hero with a strength of at least $ x $ to kill it. If the dragon’s attack power is $ y $ , then the total strength of the heroes defending the castle should be at least $ y $ .

The player can increase the strength of any hero by $ 1 $ for one gold coin. This operation can be done any number of times.

There are $ m $ dragons in the game, the $ i $ -th of them has defense equal to $ x_i $ and attack power equal to $ y_i $ . Petya was wondering what is the minimum number of coins he needs to spend to defeat the $ i $ -th dragon.

Note that the task is solved independently for each dragon (improvements are not saved).

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — number of heroes.

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ), where $ a_i $ is the strength of the $ i $ -th hero.

The third line contains a single integer $ m $ ( $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of dragons.

The next $ m $ lines contain two integers each, $ x_i $ and $ y_i $ ( $ 1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18} $ ) — defense and attack power of the $ i $ -th dragon.

输出格式

Print $ m $ lines, $ i $ -th of which contains a single integer — the minimum number of coins that should be spent to defeat the $ i $ -th dragon.

样例 #1

样例输入 #1

4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7

样例输出 #1

1
2
4
0
2

提示

To defeat the first dragon, you can increase the strength of the third hero by $ 1 $ , then the strength of the heroes will be equal to $ [3, 6, 3, 3] $ . To kill the dragon, you can choose the first hero.

To defeat the second dragon, you can increase the forces of the second and third heroes by $ 1 $ , then the strength of the heroes will be equal to $ [3, 7, 3, 3] $ . To kill the dragon, you can choose a second hero.

To defeat the third dragon, you can increase the strength of all the heroes by $ 1 $ , then the strength of the heroes will be equal to $ [4, 7, 3, 4] $ . To kill the dragon, you can choose a fourth hero.

To defeat the fourth dragon, you don’t need to improve the heroes and choose a third hero to kill the dragon.

To defeat the fifth dragon, you can increase the strength of the second hero by $ 2 $ , then the strength of the heroes will be equal to $ [3, 8, 2, 3] $ . To kill the dragon, you can choose a second hero.

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn=2e5+10;
int n,m;
ll tot;
ll a[maxn];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);tot+=a[i];}sort(a+1,a+n+1);scanf("%d",&m);while(m--){ll x,y;scanf("%lld%lld",&x,&y);if(tot<x+y){if(a[1]>x){printf("%lld\n",y-(tot-a[1]));continue;}int l=1,r=n;while(l<=r){int mid=l+r>>1;if(a[mid]>x)r=mid-1;else if(a[mid]<x)l=mid+1;else break;}int op=l+r>>1;if(y<=tot-a[op])printf("%lld\n",x-a[op]);else printf("%lld\n",x-a[op]+y-(tot-a[op]));continue;}else{if(a[1]>x){if(y>tot-a[1])printf("%lld\n",y-(tot-a[1]));else printf("0\n");continue;}int l=1,r=n;while(l<=r){int mid=l+r>>1;if(a[mid]>x)r=mid-1;else if(a[mid]<x)l=mid+1;else break;}int op=l+r>>1;int op1=op+1;if(tot==x+y){if(op1<=n)printf("%lld\n",min(x-a[op],a[op1]-x));else printf("%lld\n",x-a[op]);}else{if(y<=tot-a[op1]){if(op1<=n)printf("0\n");else printf("%lld\n",x-a[op]);}else {if(op1<=n)printf("%lld\n",min(x-a[op],y-(tot-a[op1])));else printf("%lld\n",x-a[op]);}}}}return 0;
}

相关文章:

CF1574C Slay the Dragon 题解

CF1574C Slay the Dragon 题解题目链接字面描述题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示代码实现题目 链接 https://www.luogu.com.cn/problem/CF1574C 字面描述 题面翻译 给定长度为 nnn 的序列 aaa&#xff0c;mmm 次询问&#xff0c;每次询…...

创建Django项目

创建Django项目 步骤 创建Django项目 django-admin startproject name 创建子应用 python manager.py startapp name创建工程 在使用Flask框架时&#xff0c;项目工程目录的组织与创建是需要我们自己手动创建完成的。 在django中&#xff0c;项目工程目录可以借助django提供…...

CUDA中的统一内存

文章目录1. Unified Memory Introduction1.1. System Requirements1.2. Simplifying GPU Programming1.3. Data Migration and Coherency1.4. GPU Memory Oversubscription1.5. Multi-GPU1.6. System Allocator1.7. Hardware Coherency1.8. Access Counters2. Programming Mode…...

利用机器学习(mediapipe)进行人脸468点的3D坐标检测--视频实时检测

上期文章,我们分享了人脸468点的3D坐标检测的图片检测代码实现过程,我们我们介绍一下如何在实时视频中,进行人脸468点的坐标检测。 import cv2 import mediapipe as mp mp_drawing = mp.solutions.drawing_utils mp_face_mesh = mp.solutions.face_mesh face_mesh = mp_fac…...

事务基础知识与执行计划

事务基础知识 数据库事务的概念 数据库事务是什么&#xff1f; 事务是一组原子性的SQL操作。事务由事务开始与事务结束之间执行的全部数据库操作组成。A&#xff08;原子性&#xff09;、&#xff08;C一致性&#xff09;、I&#xff08;隔离性&#xff09;、D&#xff08;持久…...

数据库实践LAB大纲 06 INDEX

索引 索引是一个列表 —— 若干列集合和这些值的记录在数据表存储位置的物理地址 作用 加快检索速度唯一性索引 —— 保障数据唯一性加速表的连接分组和排序进行检索的时候 —— 减少时间消耗 一般建立原则 经常查询的数据主键外键连接字段排序字段少涉及、重复值多的字段…...

网络安全实验室6.解密关

6.解密关 1.以管理员身份登录系统 url&#xff1a;http://lab1.xseclab.com/password1_dc178aa12e73cfc184676a4100e07dac/index.php 进入网站点击忘记密码的链接&#xff0c;进入到重置密码的模块 输入aaa&#xff0c;点击抓包&#xff0c;发送到重放模块go 查看返回的链接…...

了解并发编程

并发与并行的概念: 并发:一段时间内(假设只有一个CPU)执行多个线程,多个线程时按顺序执行 并行:同个时间点上,多个线程同时执行(多个CPU) 什么是并发编程? 在现代互联网的应用中,会出现多个请求同时对共享资源的访问情况,例如在买票,秒杀与抢购的场景中 此时就会出现线程安…...

(C语言)程序环境和预处理

问&#xff1a;1. 什么是C语言的源代码&#xff1f;2. 由于计算机只认识什么&#xff1f;因此它只能接收与执行什么&#xff1f;也就是什么&#xff1f;3. 在ANSI C的任何一种实现中&#xff0c;存在哪两个不同的环境&#xff1f;在这两种环境里面分别干什么事情&#xff1f;4.…...

RiProV2主题美化增加支付页底部提示语ritheme主题美化

美化背景 默认的RiProV2主题在支付提示页,是没有这一行提示的 希望增加根据用户类别,未登录用户购买时提示:当前为游客模式购买。或者其他提示,提示用户未登录购买不保存购买记录等。 索引关键字:ritheme主题美化之增加支付页底部提示语,RiProV2主题美化增加支付页底部提…...

2022年文章分类整理

文章目录JetPack系列Kotlin相关View相关多线程相关存储相关Gradle相关动画相关其他2022年公众号(名字&#xff1a;代码说)发表的文章&#xff0c;分类整理一下&#xff0c;方便阅读&#xff01;2023&#xff0c;继续加油&#xff0c;共勉&#xff01;JetPack系列 Android Jetp…...

蓝牙设备中的Device UUID 与 Service UUID

Device UUID也可以被称作为DeviceID。 Android 设备上扫描获取到的 deviceId 为外围设备的 MAC 地址&#xff0c;相对固定。 iOS 设备上扫描获取到的 deviceId 是系统根据外围设备 MAC 地址及发现设备的时间生成的 UUID&#xff0c;是设备上的Core Bluetooth为该设备分配的标识…...

【学习记录】PCA主成分分析 SVD奇异值分解

在看MSC-VO代码的过程中&#xff0c;大量出现了奇异值分解的内容&#xff0c;本身对这部分了解不多&#xff0c;这里补一下课&#xff0c;参考b站up主小旭学长的视频&#xff0c;链接为&#xff1a;PCA主成分分析和SVD主成分分析 PCA主成分分析 PCA根本目的在于让数据在损失尽…...

用 Python 调用 GPT-3 API

用 Python 调用 GPT-3 API GPT-3 是去年由 Open AI 推出的语言机器学习模型。它因其能够写作、写歌、写诗&#xff0c;甚至写代码而获得了广泛的媒体关注&#xff01;该工具免费使用&#xff0c;只需要注册一个电子邮件即可。 GPT-3 是一种叫 transformer 的机器学习模型。具体…...

类和对象实操之【日期类】

✨个人主页&#xff1a; Yohifo &#x1f389;所属专栏&#xff1a; C修行之路 &#x1f38a;每篇一句&#xff1a; 图片来源 The pessimist complains about the wind; the optimist expects it to change; the realist adjusts the sails. 悲观主义者抱怨风;乐观主义者期望它…...

微搭中如何实现弹性布局

我们在实际开发中经常可能会有一些社交的场景&#xff0c;比如开发一个类似朋友圈九宫格图片展示的功能。因为图片的数量不确定&#xff0c;所以需要实现图片的从左到右顺序排列。 在微搭中可以以可视化的方式设置样式。但是对于我们这类特殊需求&#xff0c;只用可视化设置显…...

九龙证券|外资强势出手!这只科创板百元股,被疯狂加仓

本周&#xff0c;北上资金净买入29.32亿元&#xff0c;连续第13周加仓A股。分商场看&#xff0c;北上资金加仓重点倾向于沪市的白马蓝筹股&#xff0c;沪股通取得50.34亿元&#xff0c;深股通则被净卖出21.02亿元。 食品饮料本周取得逾23亿元的增持&#xff0c;居职业首位&…...

51单片机最强模块化封装(4)

文章目录 前言一、创建key文件,添加key文件路径二、key文件编写三、模块化测试总结前言 本篇文章将为大家带来按键的模块化封装,这里使用到了三行按键使得我们的代码更加简便。 按键原理:独立按键 一、创建key文件,添加key文件路径 这里的操作就不过多解释了,大家自行看…...

五、Git本地仓库基本操作——分支管理

1. 什么是分支&#xff1f; master分支 我们在初始化git仓库的时候&#xff0c;会默认创建一个master分支&#xff0c;HEAD指针这时就会默认执行master分支。当我们在master分支提交&#xff08;commit&#xff09;了更新之后&#xff0c;master分支就会指向当前当前最新的co…...

vscode搭建python Django网站开发环境

这里使用pip安装的方式&#xff0c;打开命令行&#xff0c;输入执行&#xff1a; pip install django2.2这里选择安装2.2版本是因为是新的lts版本&#xff0c;长期支持稳定版。 接下来再安装pillow&#xff0c;Django底层一部分是基于pillow进行的。 pip install pillowpylint…...

questasim下载安装

questasim下载安装 https://zhuanlan.zhihu.com/p/682726018...

JDspyder:京东自动化抢购解决方案的技术实现与实战指南

JDspyder&#xff1a;京东自动化抢购解决方案的技术实现与实战指南 【免费下载链接】JDspyder 京东预约&抢购脚本&#xff0c;可以自定义商品链接 项目地址: https://gitcode.com/gh_mirrors/jd/JDspyder 在电商秒杀和限量商品抢购的激烈竞争中&#xff0c;技术手段…...

汽车电子架构演进:从分布式ECU到域控制器的技术变革与工程实践

1. 从一周新闻看汽车电子的演进脉络2012年8月的那一周&#xff0c;对于汽车电子行业来说&#xff0c;是平静水面下暗流涌动的一个缩影。当时&#xff0c;我正和几位在主机厂和Tier 1供应商工作的朋友频繁交流&#xff0c;大家普遍的感觉是&#xff0c;传统的汽车电子电气架构&a…...

星闪测距性能分析

环境HiSpark开发平台&#xff0c;两块BS21E丢包率1分钟内75次测距数据中&#xff0c;约有6次左右的数据是无效或者丢失&#xff0c;可以通过一些滤波算法过滤&#xff0c;完全可以满足小车定位的需要。测距精度目前使用的测距方案是RSSI信号强度与IQ信号结合&#xff0c;精度达…...

在线考试系统如何实现随机组卷

在现代教育和企业培训中&#xff0c;考试是评估学习效果、提升培训效率的重要工具。然而&#xff0c;传统的固定试卷模式存在诸多问题&#xff1a;题目重复率高、考试公平性难以保障、人工管理成本高。随着在线培训的发展&#xff0c;尤其是在大规模培训场景下&#xff0c;随机…...

Python一键打包exe

链接&#xff1a;https://pan.quark.cn/s/a5759c489d72...

深入浅出:用Grad-CAM解锁Swin Transformer的视觉注意力

1. 为什么需要理解Swin Transformer的视觉注意力&#xff1f; 当你第一次看到Swin Transformer在图像分类任务中表现出色时&#xff0c;可能会好奇它到底"看"到了图像的哪些部分。传统的卷积神经网络&#xff08;CNN&#xff09;通过局部感受野逐步提取特征&#xff…...

基于Rust构建命令行任务监控与通知工具:openclaw-tui-notify实践

1. 项目概述与核心价值最近在折腾一个后台数据处理脚本&#xff0c;它经常一跑就是好几个小时。问题来了&#xff0c;我总不能一直盯着终端看它什么时候结束吧&#xff1f;有时候去开个会、吃个饭&#xff0c;回来发现脚本早就跑完了&#xff0c;白白浪费了时间等结果。更头疼的…...

WSL启动器openclaw-wsl-launcher:提升Windows与Linux开发效率的桥梁工具

1. 项目概述&#xff1a;一个为WSL设计的OpenClaw启动器如果你和我一样&#xff0c;日常开发的主力环境是Windows&#xff0c;但核心的编译、部署和测试工作又离不开Linux&#xff0c;那么Windows Subsystem for Linux&#xff08;WSL&#xff09;绝对是你绕不开的利器。它让我…...

手势传感器技术:原理、实现与应用解析

1. 手势传感器技术解析&#xff1a;从原理到实现手势传感器本质上是一种基于光学原理的交互设备&#xff0c;其核心技术在于利用红外光的发射与接收来捕捉用户手势动作。与传统的电容式触摸技术不同&#xff0c;手势传感器通过主动发射红外光并测量反射信号的变化&#xff0c;实…...