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

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=1kapi+i=1maxkbpi

对于每个 1 ≤ k ≤ n 1\leq k\leq n 1kn,求如何选 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 1n2×105,1ai,bi109

时间限制 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 k1个菜品肯定是选择前 x − 1 x-1 x1个菜品中 a a a最小的 k − 1 k-1 k1个盘子。对于给定的 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 kkn恒成立。由此可得 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,mid1] 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,mid1,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样菜品&#xff0c;每样菜品都有两个权值 a i a_i ai​和 b i b_i bi​&#xff0c;如果你选择了 k k k个菜品&#xff0c;分别为 p 1 , … , p k p_1,\dots,p_k p1​,…,pk​&#xff0c;则你的花费为 ∑ i 1 k a p i max ⁡ i 1 k b p i \sum\limits_{i…...

AMEYA360:类比半导体重磅发布车规级智能高边驱动HD7xxxQ系列

致力于提供高品质芯片的国内优秀模拟及数模混合芯片设计商上海类比半导体技术有限公司(下称“类比半导体”或“类比”)宣布推出重磅新品车规级智能高边驱动HD7xxxQ系列。该系列产品包括车规级单通道高边驱动HD70xxQ和车规级双通道智能高边驱动HD70xx2Q&#xff0c;提供不同通道…...

【HarmonyOS】鸿蒙操作系统架构

HarmonyOS架构 一. 鸿蒙系统定位二. 架构整体遵从分层设计三. HarmonyOS具有的技术特性四. HarmonyOS有三大特征 其它相关推荐&#xff1a; 软考系统架构之案例篇(架构设计相关概念) 系统架构之微服务架构 系统架构设计之微内核架构 所属专栏&#xff1a;系统架构设计师 一. 鸿…...

JSON数据

一、JSON介绍 Android应用程序界面上的数据信息大部分都是通过网络请求从服务器上获取到的&#xff0c;获取到的数据类型常见的就是JSON。JSON是一种新的数据格式&#xff0c;这种格式的数据不可以直接显示到程序的界面上&#xff0c;需要将该数据解析为一个集合或对象的形式才…...

金融领域:怎么保持电力系统连续供应?

银行作为金融领域的关键机构&#xff0c;依赖于高度可靠的电力供应&#xff0c;以保持银行操作的连续性。在电力中断或电力质量问题的情况下&#xff0c;银行可能面临严重的风险&#xff0c;包括数据丢失、交易中断和客户满意度下降。 UPS监控系统在这一背景下变得至关重要&…...

批量重命名文件夹:用数字随机重命名法管理您的文件夹

在文件管理中&#xff0c;文件夹的命名是一项至关重要的任务。一个好的文件夹命名方案可以帮助我们更高效地组织和查找文件。然而&#xff0c;随着时间的推移&#xff0c;我们可能会遇到文件夹数量过多&#xff0c;难以管理和查找的问题。为了解决这个问题&#xff0c;我们可以…...

RPC与HTTP的关系

首选理清楚关系 RPC与HTTP是两个不同维度的东西 HTTP 协议&#xff08;Hyper Text Transfer Protocol&#xff09;&#xff0c;又叫做超文本传输协议&#xff0c;是一种传输协议&#xff0c;平时通过浏览器浏览网页网页&#xff0c;用到的就是 HTTP 协议。 而 RPC&#xff0…...

OpenCV #以图搜图:感知哈希算法(Perceptual hash algorithm)的原理与实验

1. 介绍 感知哈希算法&#xff08;Perceptual Hash Algorithm&#xff0c;简称pHash&#xff09; 是哈希算法的一种&#xff0c;主要用来做相似图片的搜索工作。 2. 原理 感知哈希算法&#xff08;pHash&#xff09;首先将原图像缩小成一个固定大小的像素图像&#xff0c;然后…...

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 自定义语法提示

在开发实践中&#xff0c;会使用到各种第三方组件&#xff0c;比如Element UI&#xff0c;通常的做法是到官网中复制模板再在本地根据设计要求进行修改&#xff0c;或是从其它已经实现的组件中复制相似的内容。但每次复制粘贴确实比较麻烦。 在HBuilderx中可以设置代码块来创建…...

Leetcode—2562.找出数组的串联值【简单】

2023每日刷题&#xff08;十四&#xff09; 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外部计数输入

/*----------------------------------------------- 内容&#xff1a;通过外部按键计数进入中断执行LED取反 ------------------------------------------------*/ #include<reg52.h> //包含头文件&#xff0c;一般情况不需要改动&#xff0c;头文件包含特殊功能寄存器的…...

分治法求解棋盘覆盖问题

分治法求解棋盘覆盖问题 如何应用分治法求解棋盘覆盖问题呢&#xff1f;分治的技巧在于如何划分棋盘&#xff0c;使划分后的子棋盘的大小相同&#xff0c;并且每个子棋盘均包含一个特殊方格&#xff0c;从而将原问题分解为规模较小的棋盘覆盖问题。 基本思路 棋盘覆盖问题是…...

爱写bug的小邓程序员个人博客

博客网址: http://www.006969.xyz 欢迎来到我的个人博客&#xff0c;这里主要分享我对于前后端相关技术的学习笔记、项目实战经验以及一些技术感悟。 在我的博客中&#xff0c;你将看到以下主要内容&#xff1a; 技术文章 我将会分享我在学习前后端技术过程中的一些感悟&am…...

selenium判断元素可点击、可见、可选

1、判断元素是否可以点击 判断元素是否可以点击&#xff0c;WebElement对象调用is_enabled() is_enabled()方法返回一个布尔值&#xff0c;若可点击返回&#xff1a;True。若不可点击则返回&#xff1a;False from selenium import webdriver import time from selenium.web…...

计算机网络重点概念整理-第六章 应用层【期末复习|考研复习】

计算机网络复习系列文章传送门&#xff1a; 第一章 计算机网络概述 第二章 物理层 第三章 数据链路层 第四章 网络层 第五章 传输层 第六章 应用层 第七章 网络安全 计算机网络整理-简称&缩写 文章目录 前言六、应用层6.1 网络应用模型6.1.1 客户/服务器模式C/S模型6.1.2 P…...

html2pdf

页面布局时将需要保存在同一页pdf的dom元素用div包裹&#xff0c;并为该div添加class类名&#xff0c;例如.convertPDF&#xff0c;如果有多页创建多个.convertPDF这个div&#xff0c;再循环保存pdf即可 用到了html2canvas和JsPdf这两个插件&#xff0c;自行站内搜索安装 pdf页…...

css中页面元素隐藏

display:nonevisibility:hiddenopcity:0页面中不存在存在存在重排会不会不会重绘会会不一定自身绑定事件不触发不触发能触发transition不支持支持支持子元素可复原不能能不能被遮挡的元素可触发事件能能不能 其他&#xff1a; 1.设置height&#xff0c;width&#xff0c;margi…...

dp三步问题

三步问题 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 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项目中&#xff0c;使用了联合体和结构体之间的嵌套&#xff0c;但是在访问内部的联合体和结构体的时候出现了问题&#xff0c;这篇文章作为记录&#xff0c;也希望能帮助遇到相同问题的好伙伴。 struct lept_value {union {struct str{char *s;size_t len;};double n;}…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...