CF1574C Slay the Dragon 题解
CF1574C Slay the Dragon 题解
- 题目
- 链接
- 字面描述
- 题面翻译
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 代码实现
题目
链接
https://www.luogu.com.cn/problem/CF1574C
字面描述
题面翻译
给定长度为 nnn 的序列 aaa,mmm 次询问,每次询问包含两个参数 x,yx,yx,y,你可以给序列任意位置 +1+1+1,最后你需要找出一个位置 ppp ,满足
- ap≥xa_p\ge xap≥x
- ∑i=1nai[i≠p]≥y\displaystyle\sum_{i=1}^n a_i[i\not= p] \ge yi=1∑nai[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}2≤n≤2×105,1≤m≤2×105,1≤ai,x≤1012,1≤y≤1018
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,mmm 次询问,每次询…...
创建Django项目
创建Django项目 步骤 创建Django项目 django-admin startproject name 创建子应用 python manager.py startapp name创建工程 在使用Flask框架时,项目工程目录的组织与创建是需要我们自己手动创建完成的。 在django中,项目工程目录可以借助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…...
事务基础知识与执行计划
事务基础知识 数据库事务的概念 数据库事务是什么? 事务是一组原子性的SQL操作。事务由事务开始与事务结束之间执行的全部数据库操作组成。A(原子性)、(C一致性)、I(隔离性)、D(持久…...
数据库实践LAB大纲 06 INDEX
索引 索引是一个列表 —— 若干列集合和这些值的记录在数据表存储位置的物理地址 作用 加快检索速度唯一性索引 —— 保障数据唯一性加速表的连接分组和排序进行检索的时候 —— 减少时间消耗 一般建立原则 经常查询的数据主键外键连接字段排序字段少涉及、重复值多的字段…...
网络安全实验室6.解密关
6.解密关 1.以管理员身份登录系统 url:http://lab1.xseclab.com/password1_dc178aa12e73cfc184676a4100e07dac/index.php 进入网站点击忘记密码的链接,进入到重置密码的模块 输入aaa,点击抓包,发送到重放模块go 查看返回的链接…...
了解并发编程
并发与并行的概念: 并发:一段时间内(假设只有一个CPU)执行多个线程,多个线程时按顺序执行 并行:同个时间点上,多个线程同时执行(多个CPU) 什么是并发编程? 在现代互联网的应用中,会出现多个请求同时对共享资源的访问情况,例如在买票,秒杀与抢购的场景中 此时就会出现线程安…...
(C语言)程序环境和预处理
问:1. 什么是C语言的源代码?2. 由于计算机只认识什么?因此它只能接收与执行什么?也就是什么?3. 在ANSI C的任何一种实现中,存在哪两个不同的环境?在这两种环境里面分别干什么事情?4.…...
RiProV2主题美化增加支付页底部提示语ritheme主题美化
美化背景 默认的RiProV2主题在支付提示页,是没有这一行提示的 希望增加根据用户类别,未登录用户购买时提示:当前为游客模式购买。或者其他提示,提示用户未登录购买不保存购买记录等。 索引关键字:ritheme主题美化之增加支付页底部提示语,RiProV2主题美化增加支付页底部提…...
2022年文章分类整理
文章目录JetPack系列Kotlin相关View相关多线程相关存储相关Gradle相关动画相关其他2022年公众号(名字:代码说)发表的文章,分类整理一下,方便阅读!2023,继续加油,共勉!JetPack系列 Android Jetp…...
蓝牙设备中的Device UUID 与 Service UUID
Device UUID也可以被称作为DeviceID。 Android 设备上扫描获取到的 deviceId 为外围设备的 MAC 地址,相对固定。 iOS 设备上扫描获取到的 deviceId 是系统根据外围设备 MAC 地址及发现设备的时间生成的 UUID,是设备上的Core Bluetooth为该设备分配的标识…...
【学习记录】PCA主成分分析 SVD奇异值分解
在看MSC-VO代码的过程中,大量出现了奇异值分解的内容,本身对这部分了解不多,这里补一下课,参考b站up主小旭学长的视频,链接为:PCA主成分分析和SVD主成分分析 PCA主成分分析 PCA根本目的在于让数据在损失尽…...
用 Python 调用 GPT-3 API
用 Python 调用 GPT-3 API GPT-3 是去年由 Open AI 推出的语言机器学习模型。它因其能够写作、写歌、写诗,甚至写代码而获得了广泛的媒体关注!该工具免费使用,只需要注册一个电子邮件即可。 GPT-3 是一种叫 transformer 的机器学习模型。具体…...
类和对象实操之【日期类】
✨个人主页: Yohifo 🎉所属专栏: C修行之路 🎊每篇一句: 图片来源 The pessimist complains about the wind; the optimist expects it to change; the realist adjusts the sails. 悲观主义者抱怨风;乐观主义者期望它…...
微搭中如何实现弹性布局
我们在实际开发中经常可能会有一些社交的场景,比如开发一个类似朋友圈九宫格图片展示的功能。因为图片的数量不确定,所以需要实现图片的从左到右顺序排列。 在微搭中可以以可视化的方式设置样式。但是对于我们这类特殊需求,只用可视化设置显…...
九龙证券|外资强势出手!这只科创板百元股,被疯狂加仓
本周,北上资金净买入29.32亿元,连续第13周加仓A股。分商场看,北上资金加仓重点倾向于沪市的白马蓝筹股,沪股通取得50.34亿元,深股通则被净卖出21.02亿元。 食品饮料本周取得逾23亿元的增持,居职业首位&…...
51单片机最强模块化封装(4)
文章目录 前言一、创建key文件,添加key文件路径二、key文件编写三、模块化测试总结前言 本篇文章将为大家带来按键的模块化封装,这里使用到了三行按键使得我们的代码更加简便。 按键原理:独立按键 一、创建key文件,添加key文件路径 这里的操作就不过多解释了,大家自行看…...
五、Git本地仓库基本操作——分支管理
1. 什么是分支? master分支 我们在初始化git仓库的时候,会默认创建一个master分支,HEAD指针这时就会默认执行master分支。当我们在master分支提交(commit)了更新之后,master分支就会指向当前当前最新的co…...
vscode搭建python Django网站开发环境
这里使用pip安装的方式,打开命令行,输入执行: pip install django2.2这里选择安装2.2版本是因为是新的lts版本,长期支持稳定版。 接下来再安装pillow,Django底层一部分是基于pillow进行的。 pip install pillowpylint…...
Fun-ASR-MLT-Nano-2512快速上手:Web界面操作,无需代码基础
Fun-ASR-MLT-Nano-2512快速上手:Web界面操作,无需代码基础 1. 语音识别新选择:Fun-ASR-MLT-Nano-2512 1.1 模型简介 Fun-ASR-MLT-Nano-2512是阿里通义实验室推出的轻量级多语言语音识别模型,经过开发者by113小贝的二次开发优化…...
C++ 智能指针的底层实现逻辑
C智能指针的底层实现逻辑揭秘 在C开发中,内存管理一直是程序员需要谨慎处理的难题。传统裸指针容易导致内存泄漏、悬垂指针等问题,而智能指针通过自动化资源管理,显著提升了代码的安全性和可维护性。那么,智能指针是如何在底层实…...
nli-distilroberta-base实际项目:高校招生简章关键条款与考生疑问逻辑关系库构建
nli-distilroberta-base实际项目:高校招生简章关键条款与考生疑问逻辑关系库构建 1. 项目背景与需求 高校招生简章通常包含大量专业条款和政策说明,每年都会收到大量考生关于条款理解的咨询。传统的人工解答方式存在几个痛点: 效率低下&am…...
从定时器到任务调度:用Qt QTimer和QThreadPool构建一个轻量级后台任务管理器
从定时器到任务调度:用Qt QTimer和QThreadPool构建轻量级后台任务管理器 在开发中型Qt应用时,后台任务管理往往成为架构设计的痛点。当简单的定时器无法满足复杂业务需求,当主线程被耗时任务拖累导致界面卡顿,开发者需要一套更优雅…...
小白友好!Gemma-3-12B-IT WebUI部署常见错误及修复方法
小白友好!Gemma-3-12B-IT WebUI部署常见错误及修复方法 1. 为什么你的WebUI总是打不开? 你是不是也遇到过这种情况:跟着教程一步步部署Gemma-3-12B-IT的WebUI,最后一步打开浏览器,输入地址,结果页面一直转…...
跨境电商多语种支持:SenseVoice-Small ONNX语音识别模型部署与本地化适配
跨境电商多语种支持:SenseVoice-Small ONNX语音识别模型部署与本地化适配 1. 环境准备与快速部署 SenseVoice-Small ONNX模型是一个经过量化处理的高效语音识别解决方案,特别适合跨境电商场景中的多语言语音处理需求。这个模型支持超过50种语言&#x…...
Guohua Diffusion 数据库集成方案:MySQL管理生成任务与作品元数据
Guohua Diffusion 数据库集成方案:MySQL管理生成任务与作品元数据 如果你用过Guohua Diffusion这类图像生成工具,可能会遇到一个头疼的问题:生成的图片越来越多,管理起来越来越乱。今天想找上周生成的那张“赛博朋克风格的城市夜…...
C#实战:基于WebAPI与Modbus构建EMS核心采集服务
1. 为什么需要EMS核心采集服务? 在工业现场,我们经常会遇到几十台甚至上百台智能电表、传感器等设备需要监控。这些设备可能来自不同厂家,使用不同的通信协议,数据格式也各不相同。想象一下,如果每个设备都需要单独开发…...
OpenClaw技能市场巡礼:最适合Qwen3-32B的5个实用模块
OpenClaw技能市场巡礼:最适合Qwen3-32B的5个实用模块 1. 为什么需要关注技能市场? 第一次接触OpenClaw时,我以为它只是个简单的自动化脚本集合。直到在本地部署了Qwen3-32B模型后,才发现真正的威力藏在技能市场里。这里分享一个…...
如何快速搭建个人小说离线图书馆:fanqienovel-downloader完整使用指南
如何快速搭建个人小说离线图书馆:fanqienovel-downloader完整使用指南 【免费下载链接】fanqienovel-downloader 下载番茄小说 项目地址: https://gitcode.com/gh_mirrors/fa/fanqienovel-downloader 厌倦了在线小说的网络限制和广告干扰?想要随时…...
