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

题解:ABC321D - Set Menu

题解:ABC321D - Set Menu

·题目

链接:Atcoder。

链接:洛谷。

·难度

算法难度:B。

思维难度:C。

调码难度:B。

综合评价:见洛谷链接。

·算法

枚举+二分查找。

·思路

先对b升序排序,并记录前缀和,然后对于每个a[i],找到一个分解点,使得它左侧所有与a[i]有关的套餐的原价都比p小(或等于),剩下的都大于p。那么端点左侧的采用原价购买,(l表示分界点左侧)即s[l]+a[i]*l,右侧的就采用p价格购买,花费p*(m-l)。累加每个a[i]即可。

·代价

O((n+m)*log(m)),其中O(m*log(m))是排序,O(n*log(m))是二分查找,也就是程序核心。

·细节

升序排序用sort。

·代码

#include<bits/stdc++.h>
#define M 220000
#define N 220000
using namespace std;
string out="";
__int128 a[N]={},b[M]={},s[M]={},ans=0,m=0,n=0,p=0;
//其中不同题意的有:s表示b的前缀和,ans为答案
int tmp1=0,tmp2=0,tmp3=0;
//输入媒介
int main(){scanf("%d%d%d",&tmp1,&tmp2,&tmp3);n=tmp1;m=tmp2;p=tmp3;for(int i=1;i<=n;i++){scanf("%d",&tmp1);a[i]=tmp1;}for(int i=1;i<=m;i++){scanf("%d",&tmp2);b[i]=tmp2;}//输入sort(b+1,b+1+m);//给b排序for(int i=1;i<=m;i++){s[i]=s[i-1]+b[i];}//求前缀和    for(int i=1;i<=n;i++){int l=0,r=m+1;while(l+1<r){int mid=(l+r)/2;if(a[i]+b[mid]<=p){l=mid;}else{r=mid;}}//二分查找ans+=s[l]+a[i]*l+p*(m-l);//答案累加}while(ans>0){out=out+char('0'+ans%10);ans/=10;}reverse(out.begin(),out.end());printf("%s\n",out.c_str());//输出答案return 0;
}

·注意

long long都不行,要用__int128。

相关文章:

题解:ABC321D - Set Menu

题解&#xff1a;ABC321D - Set Menu 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;B。 思维难度&#xff1a;C。 调码难度&#xff1a;B。 综合评价&#xff1a;见洛谷链接。 算法 枚举二分查找。 思路 先对b升序排序&#x…...

什么是Progressive Web App(PWA)?它们有哪些特点?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 渐进式Web App简介⭐ PWAs的主要特点⭐ 总结⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入…...

MySQL的高级SQL语句

目录 一、高级SQL语句 1、select 查询表中一个或多个字段的数据 2、distinct 不显示重复的数据记录 3、where 有条件查询 4、and与or 且与或 5、in 显示在某个范围值内 的字段的信息 6、between 显示两个值范围内的数据记录 7、order by 对字…...

基于人脸5个关键点的人脸对齐(人脸纠正)

摘要&#xff1a;人脸检测模型输出人脸目标框坐标和5个人脸关键点&#xff0c;在进行人脸比对前&#xff0c;需要对检测得到的人脸框进行对齐&#xff08;纠正&#xff09;&#xff0c;本文将通过5个人脸关键点信息对人脸就行对齐&#xff08;纠正&#xff09;。 一、输入图像…...

vue3中两个el-select下拉框选项相互影响

vue3中两个el-select下拉框选项相互影响 1、开发需求2、代码2.1 定义hooks文件2.2 在组件中使用 1、开发需求 如图所示&#xff0c;在项目开发过程中&#xff0c;遇到这样一个需求&#xff0c;常规时段中选中的月份在高峰时段中是禁止选择的状态&#xff0c;反之亦然。 2、代…...

博弈论——反应函数

反应函数 1 引言 谢老师的《经济博弈论》书中对反应函数并没有给出一般笼统的定义&#xff0c;而是将其应用与古诺模型并给出了相关解释&#xff1a;反应函数是指在无限策略的古诺博弈模型中&#xff0c;博弈方的策略有无限多种&#xff0c;因此各个博弈方的最佳对策也有无限…...

UE5读取json文件

一、下载插件 在工程中启用 二、定义读取外部json文件的函数&#xff0c;参考我之前的文章 ue5读取外部文件_艺菲的博客-CSDN博客 三、读取文件并解析为json对象 这里Load Text就是自己定义的函数&#xff0c;ResourceBundle为一个字符串常量&#xff0c;通常是读取的文件夹…...

Vue中的插槽--组件复用,内容自定义

插槽 文章目录 插槽插槽-默认插槽插槽-后备内容&#xff08;设置默认值&#xff09;插槽-具名插槽插槽–作用域插槽 插槽-默认插槽 作用&#xff1a;让组件内部的一些结构支持自定义 需求&#xff1a;要在页面中显示一个对话框,封装成一个组件&#xff08;对话框有很多功能是类…...

完全指南:mv命令用法、示例和注意事项 | Linux文件移动与重命名

文章目录 mv命令使用指南1. 简介什么是mv命令&#xff1f;mv命令的作用和功能是什么&#xff1f; 2. 基本用法基本语法格式如何移动文件&#xff1f;如何重命名文件&#xff1f;如何移动和重命名目录&#xff1f; 3. 高级用法使用通配符进行批量移动和重命名使用选项进行文件移…...

gitee生成公钥和远程仓库与本地仓库使用验证

参考文档&#xff1a; https://help.gitee.com/base/account/SSH%E5%85%AC%E9%92%A5%E8%AE%BE%E7%BD%AE(1)通过命令ssh-keygen 生成SSH key -t key类型 -c注释 ssh-keygen -t ed25519 -C "Gitee SSH Key" (2)按三次回车 (3)查看生成的 SSH 公钥和私钥&#xff1a; …...

请求后端接口413

当在进行HTTP请求时出现"413 Request Entity Too Large"错误时&#xff0c;通常是因为请求体的大小超过了服务器的配置限制。这个错误提示表明服务器拒绝接受过大的请求。 此时一般还未到后端服务&#xff0c;是被后端的ngnix代理服务器拦截的&#xff0c;所以可以检…...

HarmonyOS之 开发环境搭建

一 鸿蒙简介&#xff1a; 1.1 HarmonyOS是华为自研的一款分布式操作系统&#xff0c;兼容Android&#xff0c;但又区别Android&#xff0c;不仅仅定位于手机系统。更侧重于万物物联和智能终端&#xff0c;目前已更新到4.0版本。 1.2 HarmonyOS软件编程语言是ArkTS&#xff0c…...

QTC++ day12

注册登录界面 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QIcon> #include <QPushButton> #include <QLineEdit> #include <QLabel> #include <QDebug> #include <QMessageBox>//消息对话框类 #inc…...

Vue3中使用Proxy API取代defineProperty API的原因

目录 一、前言 二、defineProperty API的限制和问题 三、Proxy API的优势和特性 四、Vue3.0中使用Proxy API的原因 五、Proxy API的局限性和注意事项 一、前言 Vue3.0是Vue.js框架的最新版本&#xff0c;它在底层进行了许多重要的改进。其中最引人注目的变化之一是它转而…...

构建工具Webpack简介

一、构建工具 当我们习惯了Node中使用ES模块化编写代码以后&#xff0c;用原生的HTML、CSS、JS这些东西会感觉到各种不便。比如&#xff1a;不能放心的使用模块化规范&#xff08;浏览器兼容性问题&#xff09;、即使可以使用模块化规范也会面临模块过多时的加载问题。 这时候…...

Docker部署单点Elasticsearch与Kibana

一 、 创建网络 因为需要部署kibana容器&#xff0c;因此需要让es和kibana容器互联。这里创建一个网络&#xff1a; docker network create es-net # 创建一个网络名称为:es-net 二 、拉取并加载镜像 方式一 docker pull elasticsearch:7.12.1 版本为elasticsearch的7…...

opencv实现仿射变换和透射变换

##1&#xff0c; 什么是仿射变换&#xff1f; 代码实现 import numpy as np import cv2 as cv import matplotlib.pyplot as plt#设置字体 from pylab import mpl mpl.rcParams[font.sans-serif] [SimHei]#图像的读取 img cv.imread("lena.png")#仿射变换 row…...

抖音seo账号矩阵源码系统

1. 开通多个抖音账号&#xff0c;并将它们归纳为一个账号矩阵系统。 2. 建立一个统一的账号管理平台&#xff0c;以便对这些账号进行集中管理&#xff0c;包括账号信息、内容发布、社区交互等。 3. 招募专业的运营团队&#xff0c;对每个账号进行精细化运营&#xff0c;包括内…...

性能优化之防抖

方法1&#xff1a;利用lodash库提供的防抖来处理 方法2&#xff1a;手写一个防抖函数来处理 需求&#xff1a;鼠标在盒子上移动&#xff0c;鼠标停止500ms之后&#xff0c;里面的数字才会变化1 方法一&#xff1a;利用lodash库实现防抖 <!DOCTYPE html> <html lang&…...

postgresql用户和角色

postgresql用户和角色 简述创建角色角色属性登录特权超级用户创建数据库创建角色启动复制密码修改角色属性 对象授权撤销授权组和成员删除角色 简述 PostgreSQL 通过角色的概念来控制数据库的访问权限。角色又包含了两种概念&#xff0c;具有登录 权限的角色称为用户&#xff…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...