给定一个长度为 \(n\) 的序列 \(a\) 和一个整数 \(k\),构造一个序列 \(b\) 使得满足以下条件:
\(0\leq b_i\leq a_i\)
\(\sum\limits_{i=1}^{n}b_i=k\)
最大化 \(\sum\limits_{i=1}^{n}a_ib_i-b_i^3\)。
\(\texttt{Data Range:}n\leq 10^5,k\leq 10^{14}\)
神仙题。
考虑先设 \(b_i\) 为 \(0\),相当于能操作 \(k\) 次,每次能把某个 \(b_i+1\)。
考虑设 \(f(i,x)=a_ix-x^3\),那么我们有
注意到这东西在整数域上是单调递减的,于是可以按照求最大函数值的那个套路来,但是时间复杂度是 \(O(k\log n)\) 的,无法通过。
注意到我们取出来的最大函数值值是单调不升的,所以可以考虑二分一下最后一次操作对答案的贡献是什么。对于当前考虑的值我们可以通过二分来解一下某个 \(i\) 至少需要操作几次才能大于等于这个最大增量,最后 check 一下 \(\sum b_i\) 就好了。
然后由于最大函数值单调不升而不是单调递减,所以外面的二分最好不要二分到一个确切的值,而是二分到一个长度为 \(2\) 的区间,然后在 check 两个端点。
这样子可能有些时候操作次数还有剩余,于是就可以最后调整一下值就差不多了。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MAXN=2e5+51,inf=1e18;
ll n,kk,l,r,mid,sm;
ll u[MAXN],v[MAXN];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!=‘-‘)
{
ch=getchar();
}
if(ch==‘-‘)
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-‘0‘);
ch=getchar();
}
return num*neg;
}
inline ll f(ll u,ll x)
{
return u==x?inf:u-3*x*x+3*x-1;
}
inline ll calc(ll x,ll lim)
{
ll l=1,r=u[x],mid,res=u[x];
while(l<=r)
{
mid=(l+r)>>1;
f(u[x],mid)<=lim?r=mid-1,res=mid:l=mid+1;
}
return res;
}
inline ll check(ll mid)
{
sm=0;
for(register int i=1;i<=n;i++)
{
sm+=(v[i]=calc(i,mid));
}
return sm<kk;
}
int main()
{
n=read(),kk=read();
for(register int i=1;i<=n;i++)
{
u[i]=read(),l=min(l,f(u[i],u[i]-1)),r=max(r,f(u[i],0));
}
while(r-l>=2)
{
mid=(l+r)>>1;
check(mid)?r=mid:l=mid;
}
r=check(l)?l:r,check(r),kk-=sm;
for(register int i=1;i<=n;i++)
{
kk&&v[i]<u[i]&&f(u[i],v[i])==r?v[i]++,kk--:1;
}
for(register int i=1;i<=n;i++)
{
printf("%lld ",v[i]);
}
}
CodeForces 1344D Résumé Review
原文:https://www.cnblogs.com/Karry5307/p/13731799.html