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;}…...
 
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
 
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
 
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
 
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
 
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
 
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
 
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
 
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
