Noip 提高组 2011 Day2 T2 聪明的质检员 二分法

2024-03-30 16:38

本文主要是介绍Noip 提高组 2011 Day2 T2 聪明的质检员 二分法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1到n 逐一编号,每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是:

1 、给定m 个区间[Li,Ri];

2 、选出一个参数 W;

3 、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值Yi:

这批矿产的检验结果Y 为各个区间的检验值之和。即:Y1+Y2...+Ym

若这批矿产的检验结果与所给标准值S 相差太多,就需要再去检验另一批矿产。小T

不想费时间去检验另一批矿产,所以他想通过调整参数W 的值,让检验结果尽可能的靠近

标准值S,即使得S-Y 的绝对值最小。请你帮忙求出这个最小值。

输入输出格式

输入格式:

输入文件qc.in 。

第一行包含三个整数n,m,S,分别表示矿石的个数、区间的个数和标准值。

接下来的n 行,每行2个整数,中间用空格隔开,第i+1 行表示 i 号矿石的重量 wi 和价值vi。

接下来的m 行,表示区间,每行2 个整数,中间用空格隔开,第i+n+1 行表示区间[Li,Ri]的两个端点Li 和Ri。注意:不同区间可能重合或相互重叠。

输出格式:

输出文件名为qc.out。

输出只有一行,包含一个整数,表示所求的最小值。

输入输出样例

输入样例#1:
5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3 
输出样例#1:
10

说明

【输入输出样例说明】

当W 选4 的时候,三个区间上检验值分别为 20、5 、0 ,这批矿产的检验结果为 25,此

时与标准值S 相差最小为10。

【数据范围】

对于10% 的数据,有 1 ≤n ,m≤10;

对于30% 的数据,有 1 ≤n ,m≤500 ;

对于50% 的数据,有 1 ≤n ,m≤5,000;

对于70% 的数据,有 1 ≤n ,m≤10,000 ;

对于100%的数据,有 1 ≤n ,m≤200,000,0 < wi, vi≤10^6,0 < S≤10^12,1 ≤Li ≤Ri ≤n 。






传送门

看到W是全局的,也就是说W增加了那么产生的值变小,

W减小产生的值增大。

假设当前的值为t,标准为S,那么当t<S,显然让t逼近S,也就是W减小即可,

而t>S的时候,让W增大以减小t。

那么发现了W的二分性质,直接二分W并且求出t的值并且判定即可。

如何判定也很简单,留下Wi>W的,O(N)作一个前缀和,然后O(M)累计每个区间即可。






#include<bits/stdc++.h>
#define ll long long
using namespace std;
const intN=200005;
int n,m,W[N],l[N],r[N];
ll S,sumW[N],sum[N],V[N];
ll get(int W_S){sumW[0]=0LL,sum[0]=0LL;for (int i=1;i<=n;i++){sumW[i]=sumW[i-1],sum[i]=sum[i-1];if (W[i]>=W_S) sumW[i]+=V[i],sum[i]++;}ll tt=0LL;for (int i=1;i<=m;i++)tt+=(sumW[r[i]]-sumW[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);return tt;
}
int main(){scanf("%d%d%lld",&n,&m,&S);int L=0,R=0;for (int i=1;i<=n;i++)scanf("%d%lld",&W[i],&V[i]),R=max(R,W[i]);for (int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);R++;int mid;ll ans=(ll)(1e12);while (L<R){mid=(L+R+1)>>1;ll t=get(mid);ans=min(ans,abs(t-S));if (t<S) R=mid-1;else L=mid;}printf("%lld\n",ans);return 0;
}


这篇关于Noip 提高组 2011 Day2 T2 聪明的质检员 二分法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862012

相关文章

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

如何提高开发的效率,让老板不知所措的给你发工资

设计模式 UML JSP 编程 数据结构 1.你可能会常常发现,写了一段代码后,编译程序时是一大堆的出错 (原因:语法不熟)  ──别担心,这是每个程序员必须经历的事,这时候你就需要更大的耐心及细心,对每一行代码进行仔细人阅读并改正,这个很重要,这可以培养你的理解代码能力,所以要常读程序,不要等到程序运行以后才知道你的程序的结果。  ──如何避免:在写代码以前,要认真的学习计算机语

Java预备知识 - day2

1.IDEA的简单使用与介绍 1.1 IDEA的项目工程介绍 Day2_0904:项目名称 E:\0_code\Day2_0904:表示当前项目所在路径 .idea:idea软件自动生成的文件夹,最好不要动 src:src==sourse→源,我们的源代码就放在这个文件夹之内 Day2_0904.iml:也是自动生成的文件,不要动 External Libraries:外部库 我这

Java开发实例大全提高篇——Applet的应用

开发十年,就只剩下这套架构体系了! >>>    第21章  Applet的应用 21.1  Applet在html中的使用 实例549  在html中显示Applet HtmlShowApplet.java     public void paint(Graphics g){         g.drawString("html文件已经运行", 50, 50);// 绘制文本

Java开发实例大全提高篇——Java安全

开发十年,就只剩下这套架构体系了! >>>    第6篇  Java安全与Applet应用篇 第20章  Java安全 20.1  Java对称加密 实例531  使用BASE64加密     public static String encryptBASE64(byte[] data) {         //加密数据         return (new BASE64Encoder()

2024国赛论文拿奖快对照这几点及评阅要点,勿踩雷区!(国赛最后冲刺,提高获奖概率)

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 2024“高教社杯”全国大学生数学建模竞赛已过去第三个夜晚,小伙伴们都累了没有,如果感到思维滞涩,别忘了稍作休息,放松一下自己,准备迎接国赛非常重要的收尾阶段——论文。 国赛这几天的努力最后都

C++提高编程三(vector容器、deque容器)

文章目录 vector容器vector赋值操作vector容量和大小vector插入和删除vector数据存取vector互换容器vector预留空间deque容器构造函数deque赋值操作deque大小操作deque 插入和删除deque 数据存取deque 排序 vector容器 vector容器数据结构和数组相似,也称为单端数组。区别在于数组是静态空间,vector可以

随着人们网络安全意识提高,软件架构设计与评估也成为重中之重

目录 案例 【题目】 【问题 1】(13 分) 【问题 2】(12分) 【答案】 【问题 1】答案 【问题 2】答案 相关推荐 案例         阅读以下关于软件架构设计与评估的叙述,回答问题 1 和问题 2。 【题目】         某电子商务公司为正更好地管理用户,提升企业销售业绩,拟开发一套用户管理系统。该系统的基本功能是根据用户的消费级别、消费历史、信