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

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

5 2 5 2 6 3 1 2 5

输出 #2

5

说明/提示

【样例说明】

样例111中，k=2k=2k=2时，每个人的快乐值分别为3,4,4,4,33,4,4,4,33,4,4,4,3，满足要求。

样例222中，k=5k=5k=5时，每个人的快乐值分别为5,7,7,7,75,7,7,7,75,7,7,7,7，满足要求。

【数据范围】

对于10%10\%10%的数据，满足n=1n=1n=1。

对于30%30\%30%的数据，满足n≤300n\le 300n≤300。

对于60%60\%60%的数据，满足n≤5000n\le 5000n≤5000。

对于另外10%10\%10%的数据，满足m=1m=1m=1。

对于100%100\%100%的数据，满足1≤m≤n≤1061\le m\le n\le 10^61≤m≤n≤106，0≤ai≤1090\le a_i\le 10^90≤ai​≤109，1≤bi≤n1\le b_i\le n1≤bi​≤n且bib_ibi​互不相同。

本题输入量较大，请注意使用合理的输入方式。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[1000005],ans,m,b,l=1,r,mid;bools[1000005];longlongc[1000005];inlineboolcheck(intk){queue<int>q;longlongsum=0;memset(c,0,sizeof(c));for(inti=1;i<=n;i++){sum-=q.size();if(!q.empty()&&i-q.front()>=k)q.pop();if(s[i])sum+=k,q.push(i);c[i]+=sum;}while(!q.empty())q.pop();sum=0;for(inti=n;i;i--){sum-=q.size();if(!q.empty()&&q.front()-i>=k)q.pop();if(s[i])sum+=k,q.push(i);c[i]+=sum;if(s[i])c[i]-=k;//注意特判，如果 i 本身发了工资，那么会被统计两次，需要减去重复的。}for(inti=1;i<=n;i++)if(c[i]<a[i])return0;return1;}intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i],r=max(r,a[i]);for(inti=1;i<=m;i++)cin>>b,s[b]=1;r+=n;//需求最高的人不一定发工资，所以加上 n 之后才是真正的二分上限。while(l<=r){mid=(l+r)>>1;if(check(mid))ans=mid,r=mid-1;elsel=mid+1;}cout<<ans;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容