P9029 [COCI 2022/2023 #1] Čokolade题目背景Lana 和 Fran 正在参观一家巧克力工厂现在他们想买些巧克力。题目描述巧克力工厂里有nnn块不同的巧克力其中第iii块的价格为cic_ici​。Lana 和 Fran 想买mmm块巧克力。Fran 有一个消费方案•如果巧克力价格低于kkk元这块巧克力的费用将全部由 Lana 支付。•否则Lana 将支付kkk元而 Fran 将支付其余的部分即ci−kc_i−kci​−k元。Lana 对 Fran 的方案不满意想要报复 Fran。设lll为 Lana 需要支付的金额fff为 Fran 需要支付的金额。Lana 将选择使l−fl−fl−f的值最小的购买方案。由于 Fran 还在犹豫不知道要买多少巧克力所以 Lana 想知道对于给出的qqq种不同的购买方案kik_iki​和mim_imi​每种方案l−fl−fl−f的最小值。输入格式第一行包含两个整数nnn和qqq分别表示巧克力的数量和询问数量。第二行包含nnn个整数cic_ici​依次表示每块巧克力的价格。接下来qqq行每行包含两个整数kik_iki​和mim_imi​分别表示 Fran 的付款阈值和购买的巧克力总数量。输出格式输出qqq行每行一个整数表示 Lana 询问的答案。输入输出样例 #1输入 #15 2 1 9 22 10 19 18 4 5 2输出 #134 -21输入输出样例 #2输入 #27 4 1 5 4 3 7 11 9 5 4 5 7 7 3 4 5输出 #24 16 7 1输入输出样例 #3输入 #33 3 5 6 7 10 1 5 3 3 3输出 #35 12 0说明/提示子任务分值特殊性质111151515n,q≤1000,ci,ki≤106n,q \leq 1000,c_i,k_i\leq 10^6n,q≤1000,ci​,ki​≤106222202020所有询问的kkk都相等333353535无特殊性质对于100%100\%100%的数据1≤mi≤n,q≤105,1≤ci,ki≤1091\leq m_i\leq n,q\leq 10^5,1\leq c_i,k_i \leq 10^91≤mi​≤n,q≤105,1≤ci​,ki​≤109。本题满分707070分。C实现#includebits/stdc.h#defineintlonglong//坏习惯usingnamespacestd;constintmaxn1e55;inta[maxn],sum[maxn],n,q;main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);//优化cinnq;for(inti1;in;i)cina[i];sort(a1,an1);for(inti1;in;i)sum[i]sum[i-1]a[i];//前缀和while(q--){intk,m;cinkm;intrrlower_bound(a1,an1,k)-a-1;intl0,rmin(m,rr),mid;while(lr){midlr11;intxlower_bound(a1,an1,k*2-a[mid])-a-1;//依次枚举选的边界if(n-xmidm)lmid;elsermid-1;//若变差则变大变好则变小}coutsum[l]2*k*(m-l)sum[n-ml]-sum[n]\n;//前r个的和在原始r以内加上m-r个后面数的和}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容