NOIP2023模拟6联测27 点餐
题目大意
有 n n n样菜品,每样菜品都有两个权值 a i a_i ai和 b i b_i bi,如果你选择了 k k k个菜品,分别为 p 1 , … , p k p_1,\dots,p_k p1,…,pk,则你的花费为
∑ i = 1 k a p i + max  i = 1 k b p i \sum\limits_{i=1}^ka_{p_i}+\max\limits_{i=1}^kb_{p_i} i=1∑kapi+i=1maxkbpi
对于每个 1 ≤ k ≤ n 1\leq k\leq n 1≤k≤n,求如何选 k k k个菜品才能使花费最小,并输出最小花费。
1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i , b i ≤ 1 0 9 1\leq n\leq 2\times 10^5,1\leq a_i,b_i\leq 10^9 1≤n≤2×105,1≤ai,bi≤109
时间限制 2000 m s 2000ms 2000ms,空间限制 512 M B 512MB 512MB。
题解
前置知识:可持久化线段树(主席树)
首先,我们考虑如何求 k k k固定时的答案。将所有菜品按 b b b值从小到大排序,如果 b b b值相同则按 a a a值从小到大排序。枚举第 x x x个菜品作为选中的 b b b最大的菜品,那么剩下的 k − 1 k-1 k−1个菜品肯定是选择前 x − 1 x-1 x−1个菜品中 a a a最小的 k − 1 k-1 k−1个盘子。对于给定的 k k k和 x x x,用可持久化线段树可以用 O ( n log  n ) O(n\log n) O(nlogn)的时间复杂度来求出对应方案的值,我们将其记为 w ( k , x ) w(k,x) w(k,x)。
令 f ( k ) f(k) f(k)表示在取 k k k个菜品时能得到最优解的 x x x,对于两个不同的决策 x , y x,y x,y( x < y x<y x<y),若 w ( k , x ) ≥ w ( k , y ) w(k,x)\geq w(k,y) w(k,x)≥w(k,y),那么增大 k k k之后因为 y y y的可选择范围包含了 x x x的可选择范围,所以 y y y新选的 a a a值一定不大于 x x x新选的 a a a值,即 w ( k ′ , x ) ≥ w ( k ′ , y ) w(k',x)\geq w(k',y) w(k′,x)≥w(k′,y)对 k ≤ k ′ ≤ n k\leq k'\leq n k≤k′≤n恒成立。由此可得 f ( 1 ) ≤ f ( 2 ) ≤ ⋯ ≤ f ( n ) f(1)\leq f(2)\leq\cdots\leq f(n) f(1)≤f(2)≤⋯≤f(n),即最优决策具有单调性,可以用分治求解。
在分治的时候,用 s o l v e ( s l , s r , l , r ) solve(sl,sr,l,r) solve(sl,sr,l,r)表示用 x ∈ [ l , r ] x\in [l,r] x∈[l,r]来给 k ∈ [ s l , s r ] k\in [sl,sr] k∈[sl,sr]计算答案。一开始是 s o l v e ( 1 , n , 1 , n ) solve(1,n,1,n) solve(1,n,1,n),将其分成若干个子问题分别来解决。对于每个子问题,令 m i d = ( s l + s r ) / 2 mid=(sl+sr)/2 mid=(sl+sr)/2,则我们先在 [ l , r ] [l,r] [l,r]中找到 f ( m i d ) f(mid) f(mid),设 f ( m i d ) = p o s f(mid)=pos f(mid)=pos,则 [ s l , m i d − 1 ] [sl,mid-1] [sl,mid−1]的 f f f值在 [ l , p o s ] [l,pos] [l,pos]上, [ m i d + 1 , s r ] [mid+1,sr] [mid+1,sr]的 f f f值在 [ p o s , r ] [pos,r] [pos,r]上,那我们就可以将原问题分为两个子问题 s o l v e ( s l , m i d − 1 , l , p o s ) solve(sl,mid-1,l,pos) solve(sl,mid−1,l,pos)和 s o l v e ( m i d + 1 , s r , p o s , r ) solve(mid+1,sr,pos,r) solve(mid+1,sr,pos,r)。
在分治的时候,最多只会往下推 O ( log  n ) O(\log n) O(logn)层,每层需要求 O ( n ) O(n) O(n)个 w ( k , x ) w(k,x) w(k,x)的值,总共需要求 O ( n log  n ) O(n\log n) O(nlogn)个 w ( k , x ) w(k,x) w(k,x)的值,所以时间复杂度为 O ( n log  2 n ) O(n\log^2 n) O(nlog2n)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int n,tot=0,rt[N+5],re[N+5];
long long ans[N+5];
struct node{int a,b;
}w[N+5];
struct tree{int lc,rc,hv;long long s;
}tr[N*20+5];
bool cmp1(node ax,node bx){return ax.a<bx.a;}
bool cmp2(node ax,node bx){return ax.b<bx.b;}
void ch(int &r1,int r2,int l,int r,int v){r1=++tot;tr[r1]=tr[r2];if(l==r){++tr[r1].hv;tr[r1].s+=re[l];return;}int mid=l+r>>1;if(v<=mid) ch(tr[r1].lc,tr[r2].lc,l,mid,v);else ch(tr[r1].rc,tr[r2].rc,mid+1,r,v);tr[r1].hv=tr[tr[r1].lc].hv+tr[tr[r1].rc].hv;tr[r1].s=tr[tr[r1].lc].s+tr[tr[r1].rc].s;
}
long long find(int k,int l,int r,int v){if(l==r) return tr[k].s;int mid=l+r>>1;if(tr[tr[k].lc].hv>=v) return find(tr[k].lc,l,mid,v);else return find(tr[k].rc,mid+1,r,v-tr[tr[k].lc].hv)+tr[tr[k].lc].s;
}
void solve(int sl,int sr,int l,int r){if(sl>sr) return;int mid=sl+sr>>1,pos=0;for(int i=max(mid,l);i<=r;i++){long long now=w[i].b+find(rt[i],1,n,mid);if(ans[mid]>=now){ans[mid]=now;pos=i;}}solve(sl,mid-1,l,pos);solve(mid+1,sr,pos,r);
}
int main()
{
//	freopen("order.in","r",stdin);
//	freopen("order.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&w[i].a,&w[i].b);ans[i]=1e18;}sort(w+1,w+n+1,cmp1);for(int i=1;i<=n;i++){re[i]=w[i].a;w[i].a=i;}sort(w+1,w+n+1,cmp2);for(int i=1;i<=n;i++) ch(rt[i],rt[i-1],1,n,w[i].a);solve(1,n,1,n);for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);return 0;
}
相关文章:
NOIP2023模拟6联测27 点餐
题目大意 有 n n n样菜品,每样菜品都有两个权值 a i a_i ai和 b i b_i bi,如果你选择了 k k k个菜品,分别为 p 1 , … , p k p_1,\dots,p_k p1,…,pk,则你的花费为 ∑ i 1 k a p i max  i 1 k b p i \sum\limits_{i…...
 
AMEYA360:类比半导体重磅发布车规级智能高边驱动HD7xxxQ系列
致力于提供高品质芯片的国内优秀模拟及数模混合芯片设计商上海类比半导体技术有限公司(下称“类比半导体”或“类比”)宣布推出重磅新品车规级智能高边驱动HD7xxxQ系列。该系列产品包括车规级单通道高边驱动HD70xxQ和车规级双通道智能高边驱动HD70xx2Q,提供不同通道…...
 
【HarmonyOS】鸿蒙操作系统架构
HarmonyOS架构 一. 鸿蒙系统定位二. 架构整体遵从分层设计三. HarmonyOS具有的技术特性四. HarmonyOS有三大特征 其它相关推荐: 软考系统架构之案例篇(架构设计相关概念) 系统架构之微服务架构 系统架构设计之微内核架构 所属专栏:系统架构设计师 一. 鸿…...
 
JSON数据
一、JSON介绍 Android应用程序界面上的数据信息大部分都是通过网络请求从服务器上获取到的,获取到的数据类型常见的就是JSON。JSON是一种新的数据格式,这种格式的数据不可以直接显示到程序的界面上,需要将该数据解析为一个集合或对象的形式才…...
 
金融领域:怎么保持电力系统连续供应?
银行作为金融领域的关键机构,依赖于高度可靠的电力供应,以保持银行操作的连续性。在电力中断或电力质量问题的情况下,银行可能面临严重的风险,包括数据丢失、交易中断和客户满意度下降。 UPS监控系统在这一背景下变得至关重要&…...
 
批量重命名文件夹:用数字随机重命名法管理您的文件夹
在文件管理中,文件夹的命名是一项至关重要的任务。一个好的文件夹命名方案可以帮助我们更高效地组织和查找文件。然而,随着时间的推移,我们可能会遇到文件夹数量过多,难以管理和查找的问题。为了解决这个问题,我们可以…...
 
RPC与HTTP的关系
首选理清楚关系 RPC与HTTP是两个不同维度的东西 HTTP 协议(Hyper Text Transfer Protocol),又叫做超文本传输协议,是一种传输协议,平时通过浏览器浏览网页网页,用到的就是 HTTP 协议。 而 RPC࿰…...
 
OpenCV #以图搜图:感知哈希算法(Perceptual hash algorithm)的原理与实验
1. 介绍 感知哈希算法(Perceptual Hash Algorithm,简称pHash) 是哈希算法的一种,主要用来做相似图片的搜索工作。 2. 原理 感知哈希算法(pHash)首先将原图像缩小成一个固定大小的像素图像,然后…...
Android多张图片rotation旋转角度叠加/重叠堆放
Android多张图片rotation旋转角度叠加/重叠堆放 <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"…...
 
HBuilderX 自定义语法提示
在开发实践中,会使用到各种第三方组件,比如Element UI,通常的做法是到官网中复制模板再在本地根据设计要求进行修改,或是从其它已经实现的组件中复制相似的内容。但每次复制粘贴确实比较麻烦。 在HBuilderx中可以设置代码块来创建…...
 
Leetcode—2562.找出数组的串联值【简单】
2023每日刷题(十四) Leetcode—2562.找出数组的串联值 实现代码 long long findTheArrayConcVal(int* nums, int numsSize){int left 0;int right numsSize - 1;long long sum 0;while(left < right) {if(left right) {sum nums[left];break;}…...
T0外部计数输入
/*----------------------------------------------- 内容:通过外部按键计数进入中断执行LED取反 ------------------------------------------------*/ #include<reg52.h> //包含头文件,一般情况不需要改动,头文件包含特殊功能寄存器的…...
 
分治法求解棋盘覆盖问题
分治法求解棋盘覆盖问题 如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。 基本思路 棋盘覆盖问题是…...
 
爱写bug的小邓程序员个人博客
博客网址: http://www.006969.xyz 欢迎来到我的个人博客,这里主要分享我对于前后端相关技术的学习笔记、项目实战经验以及一些技术感悟。 在我的博客中,你将看到以下主要内容: 技术文章 我将会分享我在学习前后端技术过程中的一些感悟&am…...
 
selenium判断元素可点击、可见、可选
1、判断元素是否可以点击 判断元素是否可以点击,WebElement对象调用is_enabled() is_enabled()方法返回一个布尔值,若可点击返回:True。若不可点击则返回:False from selenium import webdriver import time from selenium.web…...
 
计算机网络重点概念整理-第六章 应用层【期末复习|考研复习】
计算机网络复习系列文章传送门: 第一章 计算机网络概述 第二章 物理层 第三章 数据链路层 第四章 网络层 第五章 传输层 第六章 应用层 第七章 网络安全 计算机网络整理-简称&缩写 文章目录 前言六、应用层6.1 网络应用模型6.1.1 客户/服务器模式C/S模型6.1.2 P…...
 
html2pdf
页面布局时将需要保存在同一页pdf的dom元素用div包裹,并为该div添加class类名,例如.convertPDF,如果有多页创建多个.convertPDF这个div,再循环保存pdf即可 用到了html2canvas和JsPdf这两个插件,自行站内搜索安装 pdf页…...
css中页面元素隐藏
display:nonevisibility:hiddenopcity:0页面中不存在存在存在重排会不会不会重绘会会不一定自身绑定事件不触发不触发能触发transition不支持支持支持子元素可复原不能能不能被遮挡的元素可触发事件能能不能 其他: 1.设置height,width,margi…...
 
dp三步问题
三步问题 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 class Solution { public:int waysToStep(int n) {vector<int> dp(n1,1);if(n1) return 1;dp[1]1;dp[2]2;for(int i3; i<n1; i){dp[i] ((dp[i-1]dp[i-2])%1000000007dp[i-3])%100…...
结构体和联合体嵌套访问
在JSON项目中,使用了联合体和结构体之间的嵌套,但是在访问内部的联合体和结构体的时候出现了问题,这篇文章作为记录,也希望能帮助遇到相同问题的好伙伴。 struct lept_value {union {struct str{char *s;size_t len;};double n;}…...
 
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
 
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
 
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
 
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
 
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
 
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
