题目:
链接:https://ac.nowcoder.com/acm/contest/13977/B
思路: 这个活动每过n轮就会发生循环,所以只需要考虑前n轮的情况,假设现在是x轮,每一轮每个人会消耗s点分数(等效为给当前的人ns点分数,但本轮消耗s点),所以当前轮数前x个人获得了ns的点数,后面的人什么都没有获得。最小值就是前面的人的点数和后面的人的点数的较小值减去x*s。
代码:
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll num[200000];
ll pre[200000];
ll suf[200000];
int main(){
ll n,s;
cin>>n>>s;
pre[0]=1e15;
suf[n+1]=1e15;
ll ans=-1e15;
for(int i=1;i<=n;i++){
cin>>num[i];
pre[i]=min(num[i]+n*s,pre[i-1]);
}
for(int i=n;i>=1;i--){
suf[i]=min(num[i],suf[i+1]);
}
for(int i=1;i<=n;i++){
ll ok=min(pre[i]-i*s,suf[i+1]-i*s);
ans=max(ok,ans);
}
cout<<ans<<endl;
}