当前位置: 首页 > 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…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...