刷题日记day5(二分+前缀和)

题目描述

蒟蒻的第五篇博客希望大家支持

• 1314聪明的质检员

P1314 [NOIP 2011 提高组] 聪明的质监员

题目描述

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n nn个矿石，从1 11到n nn逐一编号，每个矿石都有自己的重量w i w_iwi​以及价值v i v_ivi​。检验矿产的流程是：

1. 给定m mm个区间[ l i , r i ] [l_i,r_i][li​,ri​]；
2. 选出一个参数W WW；
3. 对于一个区间[ l i , r i ] [l_i,r_i][li​,ri​]，计算矿石在这个区间上的检验值y i y_iyi​：

y i = ∑ j = l i r i [ w j ≥ W ] × ∑ j = l i r i [ w j ≥ W ] v j y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_jyi​=j=li​∑ri​​[wj​≥W]×j=li​∑ri​​[wj​≥W]vj​

其中j jj为矿石编号，[ p ] [p][p]是指示函数，若条件p pp为真返回1 11，否则返回0 00。

这批矿产的检验结果y yy为各个区间的检验值之和。即：∑ i = 1 m y i \sum\limits_{i=1}^m y_ii=1∑m​yi​。

若这批矿产的检验结果与所给标准值s ss相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数W WW的值，让检验结果尽可能的靠近标准值s ss，即使得∣ s − y ∣ |s-y|∣s−y∣最小。请你帮忙求出这个最小值。

输入格式

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

接下来的n nn行，每行两个整数，中间用空格隔开，第i + 1 i+1i+1行表示i ii号矿石的重量w i w_iwi​和价值v i v_ivi​。

接下来的m mm行，表示区间，每行两个整数，中间用空格隔开，第i + n + 1 i+n+1i+n+1行表示区间[ l i , r i ] [l_i,r_i][li​,ri​]的两个端点l i l_ili​和r i r_iri​。注意：不同区间可能重合或相互重叠。

输出格式

一个整数，表示所求的最小值。

输入输出样例 #1

输入 #1

5 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3

输出 #1

10

说明/提示

【输入输出样例说明】

当W WW选4 44的时候，三个区间上检验值分别为20 , 5 , 0 20,5,020,5,0，这批矿产的检验结果为25 2525，此时与标准值S SS相差最小为10 1010。

【数据范围】

对于10 % 10\%10%的数据，有1 ≤ n , m ≤ 10 1 ≤n,m≤101≤n,m≤10；

对于30 % 30\%30%的数据，有1 ≤ n , m ≤ 500 1 ≤n,m≤5001≤n,m≤500；

对于50 % 50\%50%的数据，有1 ≤ n , m ≤ 5 , 000 1 ≤n,m≤5,0001≤n,m≤5,000；

对于70 % 70\%70%的数据，有1 ≤ n , m ≤ 10 , 000 1 ≤n,m≤10,0001≤n,m≤10,000；

对于100 % 100\%100%的数据，有1 ≤ n , m ≤ 200 , 000 1 ≤n,m≤200,0001≤n,m≤200,000，0 < w i , v i ≤ 1 0 6 0 < w_i,v_i≤10^60<wi​,vi​≤106，0 < s ≤ 1 0 12 0 < s≤10^{12}0<s≤1012，1 ≤ l i ≤ r i ≤ n 1 ≤l_i ≤r_i ≤n1≤li​≤ri​≤n。

思路分析

注意到题目让我们最小化某一个值，这种题目往往采用二分答案的方法，有些时候我们是直接二分答案的范围，有些时候我们是二分一个中间变量的范围，再得到答案，此题为后者。我们再分析一下题目是否有某种单调性，假设起始状态给了一个无限大的基准值W，那么y就等于0，那么s-y==s，随着基准值W的减小，会让公式所求值y变小，接着目标值s-y就会变小，显然有单调性，我们确定了方法二分答案。
接着是如何具体处理这个问题，我们会发现，随着y的不断减小，目标值s-y有可能是负数，这也就是我们二分判断边界的关键逻辑，当s-y大于等于0时，我们要让y增大，即W减小，即r=mid，当s-y小于0时，我们要让y减小，即W增大，即l=mid

代码展示

#include<iostream>#include<algorithm>#include<cstring>#include<vector>#definexfirst#defineysecondusingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PLL;constintN=2*1e5+10;LL n,m,s;LL w[N],val[N],temp[N],sum_temp[N];intcnt[N],sum_cnt[N];vector<PLL>q;LLcheck(LL x){memset(cnt,0,sizeofcnt);memset(sum_cnt,0,sizeofsum_cnt);memset(sum_temp,0,sizeofsum_temp);memcpy(temp,val,sizeofval);LL ans=0;for(inti=1;i<=n;i++){if(w[i]>=x)cnt[i]++;elsetemp[i]=0;}for(inti=1;i<=n;i++)sum_cnt[i]=sum_cnt[i-1]+cnt[i];for(inti=1;i<=n;i++)sum_temp[i]=sum_temp[i-1]+temp[i];for(inti=0;i<q.size();i++){LL l=q[i].x,r=q[i].y;ans+=(LL)(sum_cnt[r]-sum_cnt[l-1])*(sum_temp[r]-sum_temp[l-1]);}returns-ans;}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>s;for(inti=1;i<=n;i++){LL x,y;cin>>x>>y;w[i]=x,val[i]=y;}while(m--){LL x,y;cin>>x>>y;q.push_back({x,y});}LL l=0,r=1e6+1;while((l+1)!=r){LL mid=(l+r)/2;if(check(mid)>=0)r=mid;elsel=mid;//cout<<l<<" "<<r<<endl;}//cout<<abs(check(l))<<endl;//cout<<abs(check(r))<<endl;cout<<min(abs(check(l)),abs(check(r)))<<endl;return0;}

细节问题

每次调用check函数都是需要初始化的，仔细读题正确翻译那个公式的意思
为什么题号是1314这让单身狗心很痛好嘛，做题还被伤害了

AI详细注释代码

#include<iostream>#include<algorithm>#include<cstring>#include<vector>#definexfirst// pair的第一个元素（区间左端点）#defineysecond// pair的第二个元素（区间右端点）usingnamespacestd;typedeflonglongLL;// 用LL避免数据溢出（结果可能很大）typedefpair<LL,LL>PLL;// 存储区间的左右端点（l,r）constintN=2*1e5+10;// 数组最大长度（适配n,m<=2e5）// 全局变量LL n,m,s;// n=矿石数，m=区间数，s=标准值LL w[N],val[N];// w[i]=第i个矿石重量，val[i]=第i个矿石价值LL temp[N],sum_temp[N];// temp[i]=筛选后的矿石价值，sum_temp=temp的前缀和intcnt[N],sum_cnt[N];// cnt[i]=标记矿石是否≥W，sum_cnt=cnt的前缀和vector<PLL>q;// 存储所有区间[l,r]// 检查函数：给定参数W=x，计算检验值与标准值s的差值（s - 总检验值）LLcheck(LL x){// 初始化前缀和/标记数组为0memset(cnt,0,sizeofcnt);memset(sum_cnt,0,sizeofsum_cnt);memset(sum_temp,0,sizeofsum_temp);// 拷贝原始价值数组到temp（后续仅修改不满足条件的位置）memcpy(temp,val,sizeofval);LL ans=0;// 存储总检验值// 1. 标记满足w[i]≥x的矿石，并清空不满足的矿石价值for(inti=1;i<=n;i++){if(w[i]>=x)cnt[i]++;// 满足条件，标记为1elsetemp[i]=0;// 不满足条件，价值置0}// 2. 计算前缀和（快速求区间内满足条件的矿石数/价值和）for(inti=1;i<=n;i++)sum_cnt[i]=sum_cnt[i-1]+cnt[i];// 前缀和：1~i中≥x的矿石数量for(inti=1;i<=n;i++)sum_temp[i]=sum_temp[i-1]+temp[i];// 前缀和：1~i中≥x的矿石价值和// 3. 遍历所有区间，计算总检验值for(inti=0;i<q.size();i++){LL l=q[i].x,r=q[i].y;// 当前区间的左右端点// 区间内满足条件的矿石数 × 区间内满足条件的矿石价值和 → 累加总检验值ans+=(LL)(sum_cnt[r]-sum_cnt[l-1])*(sum_temp[r]-sum_temp[l-1]);}returns-ans;// 返回标准值与总检验值的差值（用于二分判断）}intmain(){// 加速cin/cout，避免大数据量超时ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);// 输入基础参数：矿石数、区间数、标准值cin>>n>>m>>s;// 输入每个矿石的重量和价值for(inti=1;i<=n;i++){LL x,y;cin>>x>>y;w[i]=x,val[i]=y;}// 输入所有区间，存入vectorwhile(m--){LL x,y;cin>>x>>y;q.push_back({x,y});}// 二分查找最优W值：W范围0~1e6+1（w[i]≤1e6）LL l=0,r=1e6+1;while((l+1)!=r){// 二分终止条件：左右边界相邻LL mid=(l+r)/2;// 中间值if(check(mid)>=0)r=mid;// 差值≥0 → 需增大W，缩小右边界elsel=mid;// 差值<0 → 需减小W，扩大左边界}// 比较最终两个边界的差值绝对值，取最小值（最优解）cout<<min(abs(check(l)),abs(check(r)))<<endl;return0;}