铜陵58同城做网站,惠州市惠城区规划建设局网站,网易企业邮箱注册申请免费,学网页设计网页设计题目描述
小T 是一名质量监督员#xff0c;最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石#xff0c;从 $1$ 到 $n$ 逐一编号#xff0c;每个矿石都有自己的重量 $w_i$ 以及价值 $v_i$ 。检验矿产的流程是#xff1a;
1. 给定$ m$ 个区间 $[l_i,r_i]$#xff1b…题目描述
小T 是一名质量监督员最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石从 $1$ 到 $n$ 逐一编号每个矿石都有自己的重量 $w_i$ 以及价值 $v_i$ 。检验矿产的流程是
1. 给定$ m$ 个区间 $[l_i,r_i]$ 2. 选出一个参数 $W$ 3. 对于一个区间 $[l_i,r_i]$计算矿石在这个区间上的检验值 $y_i$
$$y_i\sum\limits_{jl_i}^{r_i}[w_j \ge W] \times \sum\limits_{jl_i}^{r_i}[w_j \ge W]v_j$$
其中 $j$ 为矿石编号。
这批矿产的检验结果 $y$ 为各个区间的检验值之和。即$\sum\limits_{i1}^m y_i$
若这批矿产的检验结果与所给标准值 $s$ 相差太多就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产所以他想通过调整参数 $W$ 的值让检验结果尽可能的靠近标准值 $s$即使得 $|s-y|$ 最小。请你帮忙求出这个最小值。
输入格式
第一行包含三个整数 $n,m,s$分别表示矿石的个数、区间的个数和标准值。
接下来的 $n$ 行每行两个整数中间用空格隔开第 $i1$ 行表示 $i$ 号矿石的重量 $w_i$ 和价值 $v_i$。
接下来的 $m$ 行表示区间每行两个整数中间用空格隔开第 $in1$ 行表示区间 $[l_i,r_i]$ 的两个端点 $l_i$ 和 $r_i$。注意不同区间可能重合或相互重叠。
输出格式
一个整数表示所求的最小值。
## 样例 #1
### 样例输入 #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 w_i,v_i≤10^6$$0 s≤10^{12}$$1 ≤l_i ≤r_i ≤n$ 。
分析这道题用到了前缀和以及二分查找的方法。
代码
#includebits/stdc.h
using namespace std;long long n, m, s; // 定义长整型变量 n, m, s
long long w[200001] {0}; // 定义长整型数组 w初始化为 0
long long v[200001] {0}; // 定义长整型数组 v初始化为 0
long long l[200001] {0}; // 定义长整型数组 l初始化为 0
long long r[200001] {0}; // 定义长整型数组 r初始化为 0
long long sum_w[200001] {0}; // 定义长整型数组 sum_w初始化为 0
long long sum_v[200001] {0}; // 定义长整型数组 sum_v初始化为 0
long long mini 1000000; // 定义最小值初始化为最大的长整型数值
long long maxi -1; // 定义最大值初始化为 -1
long long result 0; // 定义结果初始化为 0// 计算函数y参数为长整型W返回长整型值
long long y(long long W)
{long long ans 0; // 定义长整型变量 ans初始化为 0memset(sum_v, 0, sizeof(sum_v)); // 用 0 填充 sum_v 数组memset(sum_w, 0, sizeof(sum_w)); // 用 0 填充 sum_w 数组for (long long i 1; i n; i) //前缀和{// 根据w[i]的值判断是否累加sum_w和sum_v数组if (w[i] W){sum_w[i] sum_w[i - 1] 1;sum_v[i] sum_v[i - 1] v[i];}else{sum_w[i] sum_w[i - 1];sum_v[i] sum_v[i - 1];}}for (long long i 1; i m; i){// 根据sum_w和sum_v数组计算ans的值ans (sum_w[r[i]] - sum_w[l[i] - 1]) * (sum_v[r[i]] - sum_v[l[i] - 1]);}return ans; // 返回结果ans
}// 检查函数check参数为长整型ans返回布尔类型值
bool check(long long ans)
{result llabs(ans - s); // 计算result的值if (ans s){return true; // 如果ans大于s返回true}else{return false; // 如果ans不大于s返回false}
}int main()
{cin n m s; // 输入n, m, s的值for (long long i 1; i n; i){cin w[i] v[i]; // 输入w[i]和v[i]的值maxi max(maxi, w[i]); // 更新maxi的值mini min(mini, w[i]); // 更新mini的值}for (long long j 1; j m; j){cin l[j] r[j]; // 输入l[j]和r[j]的值}long long left mini, right maxi; // 定义长整型变量left和right分别赋值为mini和maxilong long mid; // 定义长整型变量midlong long ans 0x3f3f3f3f3f3f3f3f; // 在计算机编程中像0x3f3f3f3f3f3f3f3f这样的十六进制数字通常用作初始化数组或变量的初始值。这个值在算法竞赛和编程中被广泛使用通常表示无穷大或者一个非常大的数用于表示初始条件或者占位符。while (left right){mid (right left) / 2; // 计算mid的值if (check(y(mid))) // 调用check函数传入y(mid)的值如果返回true{left mid 1; // 更新left的值,减小y(mid)的值因为W增大了矿石选的更少了。}else{right mid - 1; // 更新right的值}if (ans result) // 如果ans大于result{ans result; // 更新ans的值为result}}cout ans endl; // 输出结果ansreturn 0; // 返回0
}
