P9519 pay题目描述今天是 L 公司发工资的一天。nnn名员工排成一排准备领工资编号为1∼n1\sim n1∼n第iii名员工有一个期望快乐值aia_iai​。老板非常扣在这nnn名员工中只选择了mmm名员工b1,b2,⋯ ,bmb_1,b_2,\cdots,b_mb1​,b2​,⋯,bm​发kkk元工资。员工们都非常具有同理心不仅自己获得工资时会增加快乐值当周围的员工获得工资时自己也会增加快乐值。具体地当与一名员工 A 距离为ddd的员工获得了工资A 的快乐值会增加max⁡(0,k−d)\max(0, k - d)max(0,k−d)。特别地如果 A 本身就获得了工资A 的快乐值会增加kkk。老板希望你能找到最小的整数kkk使得所有员工的快乐值不低于他的期望。输入格式第一行两个整数n,mn,mn,m。第二行nnn个整数a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​。第三行mmm个整数b1,b2,⋯ ,bmb_1,b_2,\cdots,b_mb1​,b2​,⋯,bm​。输出格式一个整数表示你求出的最小的kkk。输入输出样例 #1输入 #15 5 3 3 3 3 3 1 2 3 4 5输出 #12输入输出样例 #2输入 #25 2 5 2 6 3 1 2 5输出 #25说明/提示【样例说明】样例111中k2k2k2时每个人的快乐值分别为3,4,4,4,33,4,4,4,33,4,4,4,3满足要求。样例222中k5k5k5时每个人的快乐值分别为5,7,7,7,75,7,7,7,75,7,7,7,7满足要求。【数据范围】对于10%10\%10%的数据满足n1n1n1。对于30%30\%30%的数据满足n≤300n\le 300n≤300。对于60%60\%60%的数据满足n≤5000n\le 5000n≤5000。对于另外10%10\%10%的数据满足m1m1m1。对于100%100\%100%的数据满足1≤m≤n≤1061\le m\le n\le 10^61≤m≤n≤1060≤ai≤1090\le a_i\le 10^90≤ai​≤1091≤bi≤n1\le b_i\le n1≤bi​≤n且bib_ibi​互不相同。本题输入量较大请注意使用合理的输入方式。C实现#includebits/stdc.husingnamespacestd;intn,a[1000005],ans,m,b,l1,r,mid;bools[1000005];longlongc[1000005];inlineboolcheck(intk){queueintq;longlongsum0;memset(c,0,sizeof(c));for(inti1;in;i){sum-q.size();if(!q.empty()i-q.front()k)q.pop();if(s[i])sumk,q.push(i);c[i]sum;}while(!q.empty())q.pop();sum0;for(intin;i;i--){sum-q.size();if(!q.empty()q.front()-ik)q.pop();if(s[i])sumk,q.push(i);c[i]sum;if(s[i])c[i]-k;//注意特判如果 i 本身发了工资那么会被统计两次需要减去重复的。}for(inti1;in;i)if(c[i]a[i])return0;return1;}intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for(inti1;in;i)cina[i],rmax(r,a[i]);for(inti1;im;i)cinb,s[b]1;rn;//需求最高的人不一定发工资所以加上 n 之后才是真正的二分上限。while(lr){mid(lr)1;if(check(mid))ansmid,rmid-1;elselmid1;}coutans;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容