題意
https://vjudge.net/problem/CodeForces-460C
一個長度為 n 的序列 a ，你有 m 次操作的機會，每次操作是將其中連續的 w 個元素增加 1 ，最大化最終序列的最小值，
思路
最大化最小值，二分的套路題，
資料范圍1e5，所以我們要O（n）check，
如何能做到O（n）?
差分！
求出查分陣列后，差分的前綴和就是原陣列，如果我們要check(x)，那么每當前綴和<x時，就要c[i]+=(x-s)，c[i+w]-=(x-s)，因為可以連續給w個元素加1，所以在i+w的地方減去相應值，這樣可以最大化利用這個w，最后我們判斷累計的x-s是否小于等于m即可，
注意每次二分后要還原差分陣列！！
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll inv(ll a,ll p){return qpow(a,p-2);}
ll read()
{
ll x=0;
char ch=getchar();
while(!isdigit(ch))
{
ch=getchar();
}
while(isdigit(ch))
{
x=x*10+(ch-'0');
ch=getchar();
}
return x;
}
int n,m,w;
ll a[N],c[N];
bool check(ll x)
{
ll sum=0,res=0;
for(int i=1;i<=n;i++)
{
sum+=c[i];
if(sum<x)
{
res+=x-sum;
c[i]+=(x-sum);
if(i+w<=n)
c[i+w]-=(x-sum);
sum=x;
}
}
for(int i=1;i<=n;i++)
c[i]=a[i]-a[i-1];
return res<=m;
}
int main()
{
std::ios::sync_with_stdio(false);
n=read(),m=read(),w=read();
for(int i=1;i<=n;++i)
{
a[i]=read();
c[i]=a[i]-a[i-1];
}
ll l=1,r=1e14,mid,ans;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else
r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117883.html
標籤：其他
上一篇：資料結構導論 二 時空性
下一篇：汪博士解讀，pmbok第6版