企业官网建设流程全解析

网站地图好处,广州网站设计公司兴田德润活动,wordpress 纯净版下载地址,微信无需下载免费登录题目描述 蒟蒻的第五篇博客希望大家支持 1314聪明的质检员 P1314 [NOIP 2011 提高组] 聪明的质监员 题目描述 小 T 是一名质量监督员#xff0c;最近负责检验一批矿产的质量。这批矿产共有 nnn 个矿石#xff0c;从 111 到 nnn 逐一编号#xff0c;每个矿石都有自己的重…题目描述蒟蒻的第五篇博客希望大家支持1314聪明的质检员P1314 [NOIP 2011 提高组] 聪明的质监员题目描述小 T 是一名质量监督员最近负责检验一批矿产的质量。这批矿产共有n nn个矿石从1 11到n nn逐一编号每个矿石都有自己的重量w i w_iwi​以及价值v i v_ivi​。检验矿产的流程是给定m mm个区间[ l i , r i ] [l_i,r_i][li​,ri​]选出一个参数W WW对于一个区间[ 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_{jl_i}^{r_i}[w_j \ge W] \times \sum\limits_{jl_i}^{r_i}[w_j \ge W]v_jyi​jli​∑ri​​[wj​≥W]×jli​∑ri​​[wj​≥W]vj​其中j jj为矿石编号[ p ] [p][p]是指示函数若条件p pp为真返回1 11否则返回0 00。这批矿产的检验结果y yy为各个区间的检验值之和。即∑ i 1 m y i \sum\limits_{i1}^m y_ii1∑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 i1i1行表示i ii号矿石的重量w i w_iwi​和价值v i v_ivi​。接下来的m mm行表示区间每行两个整数中间用空格隔开第i n 1 in1in1行表示区间[ l i , r i ] [l_i,r_i][li​,ri​]的两个端点l i l_ili​和r i r_iri​。注意不同区间可能重合或相互重叠。输出格式一个整数表示所求的最小值。输入输出样例 #1输入 #15 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3输出 #110说明/提示【输入输出样例说明】当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,0000 w i , v i ≤ 1 0 6 0 w_i,v_i≤10^60wi​,vi​≤1060 s ≤ 1 0 12 0 s≤10^{12}0s≤10121 ≤ l i ≤ r i ≤ n 1 ≤l_i ≤r_i ≤n1≤li​≤ri​≤n。思路分析注意到题目让我们最小化某一个值这种题目往往采用二分答案的方法有些时候我们是直接二分答案的范围有些时候我们是二分一个中间变量的范围再得到答案此题为后者。我们再分析一下题目是否有某种单调性假设起始状态给了一个无限大的基准值W那么y就等于0那么s-ys随着基准值W的减小会让公式所求值y变小接着目标值s-y就会变小显然有单调性我们确定了方法二分答案。接着是如何具体处理这个问题我们会发现随着y的不断减小目标值s-y有可能是负数这也就是我们二分判断边界的关键逻辑当s-y大于等于0时我们要让y增大即W减小即rmid当s-y小于0时我们要让y减小即W增大即lmid代码展示#includeiostream#includealgorithm#includecstring#includevector#definexfirst#defineysecondusingnamespacestd;typedeflonglongLL;typedefpairLL,LLPLL;constintN2*1e510;LL n,m,s;LL w[N],val[N],temp[N],sum_temp[N];intcnt[N],sum_cnt[N];vectorPLLq;LLcheck(LL x){memset(cnt,0,sizeofcnt);memset(sum_cnt,0,sizeofsum_cnt);memset(sum_temp,0,sizeofsum_temp);memcpy(temp,val,sizeofval);LL ans0;for(inti1;in;i){if(w[i]x)cnt[i];elsetemp[i]0;}for(inti1;in;i)sum_cnt[i]sum_cnt[i-1]cnt[i];for(inti1;in;i)sum_temp[i]sum_temp[i-1]temp[i];for(inti0;iq.size();i){LL lq[i].x,rq[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);cinnms;for(inti1;in;i){LL x,y;cinxy;w[i]x,val[i]y;}while(m--){LL x,y;cinxy;q.push_back({x,y});}LL l0,r1e61;while((l1)!r){LL mid(lr)/2;if(check(mid)0)rmid;elselmid;//coutl rendl;}//coutabs(check(l))endl;//coutabs(check(r))endl;coutmin(abs(check(l)),abs(check(r)))endl;return0;}细节问题每次调用check函数都是需要初始化的仔细读题正确翻译那个公式的意思为什么题号是1314这让单身狗心很痛好嘛做题还被伤害了AI详细注释代码#includeiostream#includealgorithm#includecstring#includevector#definexfirst// pair的第一个元素区间左端点#defineysecond// pair的第二个元素区间右端点usingnamespacestd;typedeflonglongLL;// 用LL避免数据溢出结果可能很大typedefpairLL,LLPLL;// 存储区间的左右端点l,rconstintN2*1e510;// 数组最大长度适配n,m2e5// 全局变量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_temptemp的前缀和intcnt[N],sum_cnt[N];// cnt[i]标记矿石是否≥Wsum_cntcnt的前缀和vectorPLLq;// 存储所有区间[l,r]// 检查函数给定参数Wx计算检验值与标准值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 ans0;// 存储总检验值// 1. 标记满足w[i]≥x的矿石并清空不满足的矿石价值for(inti1;in;i){if(w[i]x)cnt[i];// 满足条件标记为1elsetemp[i]0;// 不满足条件价值置0}// 2. 计算前缀和快速求区间内满足条件的矿石数/价值和for(inti1;in;i)sum_cnt[i]sum_cnt[i-1]cnt[i];// 前缀和1~i中≥x的矿石数量for(inti1;in;i)sum_temp[i]sum_temp[i-1]temp[i];// 前缀和1~i中≥x的矿石价值和// 3. 遍历所有区间计算总检验值for(inti0;iq.size();i){LL lq[i].x,rq[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);// 输入基础参数矿石数、区间数、标准值cinnms;// 输入每个矿石的重量和价值for(inti1;in;i){LL x,y;cinxy;w[i]x,val[i]y;}// 输入所有区间存入vectorwhile(m--){LL x,y;cinxy;q.push_back({x,y});}// 二分查找最优W值W范围0~1e61w[i]≤1e6LL l0,r1e61;while((l1)!r){// 二分终止条件左右边界相邻LL mid(lr)/2;// 中间值if(check(mid)0)rmid;// 差值≥0 → 需增大W缩小右边界elselmid;// 差值0 → 需减小W扩大左边界}// 比较最终两个边界的差值绝对值取最小值最优解coutmin(abs(check(l)),abs(check(r)))endl;return0;}