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

什么是Progressive Web App(PWA)?它们有哪些特点?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 渐进式Web App简介⭐ PWAs的主要特点⭐ 总结⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 欢迎来到前端入门之旅!感兴趣的可以订阅本专栏哦!这个专栏是为那些对Web开发感兴趣、刚刚踏入…...

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

基于人脸5个关键点的人脸对齐(人脸纠正)
摘要:人脸检测模型输出人脸目标框坐标和5个人脸关键点,在进行人脸比对前,需要对检测得到的人脸框进行对齐(纠正),本文将通过5个人脸关键点信息对人脸就行对齐(纠正)。 一、输入图像…...

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

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

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

Vue中的插槽--组件复用,内容自定义
插槽 文章目录 插槽插槽-默认插槽插槽-后备内容(设置默认值)插槽-具名插槽插槽–作用域插槽 插槽-默认插槽 作用:让组件内部的一些结构支持自定义 需求:要在页面中显示一个对话框,封装成一个组件(对话框有很多功能是类…...
完全指南:mv命令用法、示例和注意事项 | Linux文件移动与重命名
文章目录 mv命令使用指南1. 简介什么是mv命令?mv命令的作用和功能是什么? 2. 基本用法基本语法格式如何移动文件?如何重命名文件?如何移动和重命名目录? 3. 高级用法使用通配符进行批量移动和重命名使用选项进行文件移…...

gitee生成公钥和远程仓库与本地仓库使用验证
参考文档: 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 公钥和私钥: …...
请求后端接口413
当在进行HTTP请求时出现"413 Request Entity Too Large"错误时,通常是因为请求体的大小超过了服务器的配置限制。这个错误提示表明服务器拒绝接受过大的请求。 此时一般还未到后端服务,是被后端的ngnix代理服务器拦截的,所以可以检…...

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

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框架的最新版本,它在底层进行了许多重要的改进。其中最引人注目的变化之一是它转而…...

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

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

opencv实现仿射变换和透射变换
##1, 什么是仿射变换? 代码实现 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. 开通多个抖音账号,并将它们归纳为一个账号矩阵系统。 2. 建立一个统一的账号管理平台,以便对这些账号进行集中管理,包括账号信息、内容发布、社区交互等。 3. 招募专业的运营团队,对每个账号进行精细化运营,包括内…...

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

postgresql用户和角色
postgresql用户和角色 简述创建角色角色属性登录特权超级用户创建数据库创建角色启动复制密码修改角色属性 对象授权撤销授权组和成员删除角色 简述 PostgreSQL 通过角色的概念来控制数据库的访问权限。角色又包含了两种概念,具有登录 权限的角色称为用户ÿ…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...