P9468 [EGOI 2023] Candy / 糖果题目背景Day 2 Problem B.题面译自 EGOI2023 candy。题目描述在伊卡古城据说有一座宫殿其财富超乎想象。在其中一个走廊中有N NN盒来自世界各地的糖果。路过的旅行者只要用黄金支付糖果的重量就可以拿走任意多的糖果。装糖果的盒子被从左到右编号为0 00到N − 1 N-1N−1。在盒子i ii中剩余有a i a_iai​单位的糖果其中a i a_iai​是一个非负整数。作为宫殿的守护者你需要移动这些盒子使得有很多糖果的盒子更靠近入口。你已知数组a 0 , a 1 , ⋯ , a N − 1 a_0,a_1,\cdots,a_{N-1}a0​,a1​,⋯,aN−1​以及整数F FF和T TT。在一次操作中你被允许交换a 0 , a 1 , ⋯ , a N − 1 a_0,a_1,\cdots,a_{N-1}a0​,a1​,⋯,aN−1​中的任意两个相邻元素。要使得数组前F FF个元素的和至少为T TT至少需要多少次操作输入格式第一行三个整数N , F , T N,F,TN,F,T。第二行N NN个整数a 0 , a 1 , ⋯ , a N − 1 a_0,a_1,\cdots,a_{N-1}a0​,a1​,⋯,aN−1​。输出格式如果不可能达成目标输出NO。否则输出一个整数表示最少操作数。输入输出样例 #1输入 #16 2 27 10 4 20 6 3 3输出 #11输入输出样例 #2输入 #26 5 5000000000 1000000000 1000000000 0 1000000000 1000000000 1000000000输出 #23输入输出样例 #3输入 #33 2 100 20 30 60输出 #3NO输入输出样例 #4输入 #41 1 100 100输出 #40说明/提示样例1 11解释在样例1 11中前两个元素的和应当至少为27 2727。一次相邻元素的交换就可以达成目标交换4 44和20 2020。在这次交换后数组变成10 20 4 6 3 3前两个元素的和为10 20 30 ≥ 27 102030\ge 27102030≥27。样例2 22解释在样例2 22中这个0 00必须一路移动到数组末尾这需要3 33次交换。样例3 33解释在样例3 33中不可能使得前两个元素和至少为100 100100我们能做到的最好结果是60 30 90 603090603090。数据范围对于全部数据1 ≤ N ≤ 100 1\le N\le 1001≤N≤1001 ≤ F ≤ N 1\le F\le N1≤F≤N0 ≤ T ≤ 10 11 0\le T\le 10^{11}0≤T≤10110 ≤ a i ≤ 10 9 0\le a_i\le 10^90≤ai​≤109。子任务一6 66分N ≤ 2 N\le 2N≤2a i ≤ 100 a_i\le 100ai​≤100T ≤ 10 9 T\le 10^9T≤109。子任务二19 1919分a i ≤ 1 a_i\le 1ai​≤1。子任务三16 1616分N ≤ 20 N\le 20N≤20。子任务四30 3030分a i ≤ 100 a_i\le 100ai​≤100。子任务五29 2929分无特殊限制。提示答案可能不在32 3232位整型范围内如果你使用 C 语言请注意溢出的可能。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintinf1e16;intdp[109][109][5009];intN,F,T,ansinf,presum0;inta[109];signedmain(){cinNFT;for(inti1;iN;i)cina[i];for(inti1;iN;i){for(intj1;jmin(i,F);j){for(intk0;ki*(i-1)/2;k){dp[i][j][k]dp[i-1][j][k];if(k-ij0)dp[i][j][k]max(dp[i-1][j-1][k-ij]a[i],dp[i][j][k]);}}}for(intk0;kN*(N-1)/2;k){if(dp[N][F][k]T)ansmin(ans,k);}if(ansinf)coutNO;elsecoutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容