页面看不到网站,wordpress更改固定链接后,深圳网站建设设计科技有限公司,卓企做的网站怎么样题意#xff1a;给定长度为nnn的自然数序列aaa和整数kkk#xff0c;要求构造长度为nnn的自然数序列bbb#xff0c;使得0≤bi≤ai,∑bik0\leq b_i\leq a_i,\sum b_ik0≤bi≤ai,∑bik#xff0c;且∑bi(ai−bi2)\sum b_i(a_i-b_i^2)∑bi(ai−bi2)最大化。 n≤105…题意给定长度为nnn的自然数序列aaa和整数kkk要求构造长度为nnn的自然数序列bbb使得0≤bi≤ai,∑bik0\leq b_i\leq a_i,\sum b_ik0≤bi≤ai,∑bik且∑bi(ai−bi2)\sum b_i(a_i-b_i^2)∑bi(ai−bi2)最大化。
n≤105n\leq 10^5n≤105
要求最大化的是b(a−b2)b(a-b^2)b(a−b2),记为f(x)x(a−x2)f(x)x(a-x^2)f(x)x(a−x2)
注意到xxx每增加111f(x)f(x)f(x)会增加Δi(x)ai−3x2−3x−1\Delta_i(x) a_i-3x^2-3x-1Δi(x)ai−3x2−3x−1
注意到对于每个iii,当x≥0x\geq 0x≥0时Δi(x)\Delta_i(x)Δi(x)单调递减题目所求就是所有数中的前kkk大之和而每个Δi\Delta_iΔi被取的一定是前面若干个所以可以套路性地维护当前的xix_ixi和一个堆每次取堆顶让对应的xi1x_i1xi1
这样复杂度是O(klogn)O(k\log n)O(klogn)无法通过
但是每次加上的Δi(x)\Delta_i(x)Δi(x)是单调递减的(废话)所以可以二分最小的dΔi(x)d\Delta_i(x)dΔi(x)再二分出每个Δi\Delta_iΔi被选了多少个判断∑xik\sum x_ik∑xik
最后∑xi\sum x_i∑xi可能小于kkk但每个位置最多只能111,直接在当前基础上暴力选k−∑xik-\sum x_ik−∑xi个
复杂度O(nlog2V)O(n\log^2V)O(nlog2V)
#include iostream
#include cctype
#include cstring
#include cstdio
#include algorithm
#define MAXN 100005
using namespace std;
typedef long long ll;
const ll INF4e18;
int a[MAXN],b[MAXN],x[MAXN],p[MAXN],n;
ll k,sum;
inline ll delta(const int a,const int x){return xa? -INF:a-3ll*x*x-3ll*x-1;}
inline bool cmp(int A,int B){return delta(a[A],x[A])delta(a[B],x[B]);}
inline bool check(ll v)
{for (int i1;in;i){if (delta(a[i],0)v) x[i]0;else{int l0,ra[i]-1,mid;while (lr){mid(lr1)1;if (delta(a[i],mid)v) rmid-1;else lmid;}x[i]l1;}}sum0;for (int i1;in;i) sumx[i];if (sumk) return false;for (int i1;in;i) b[i]x[i];return true;
}
int main()
{cinnk;for (int i1;in;i) scanf(%d,a[i]);ll l-INF,rINF,mid,ans;while (lr){mid(lr)/2;if (check(mid)) ansmid,rmid-1;else lmid1;}check(ans);for (int i1;in;i) p[i]i;sort(p1,pn1,cmp);for (int i1;ik-sum;i) b[p[i]];for (int i1;in;i) printf(%d ,b[i]);return 0;
}
