前言

热乎着的一道题，昨晚上刚考完，然而这是一场悲剧。。。。

传送门：

引用站外地址

E. Cardboard for Pictures

Codeforces

题解

题目大意

给定 $a_1 ~ a_n$ 和 $c$ ，求 $(a_1+2\times w)^2+(a_2+2\times w)^2+...+(a_n+2\times w)^2=c$ 时 $w$ 的最小值

解析

我们来化简一下这个式子：

$(a_1+2\times w)^2+(a_2+2\times w)^2+...+(a_n+2\times w)^2$

根据完全平方公式 $(a+b)^2=a^2+b^2+2ab$ （对！初一数学！）可得

原式 $=(a_1)^2+(2\times w)^2+2\times a_1\times (2\times w)+(a_2)^2+(2\times w)^2+2\times a_2\times (2\times w)+...+(a_n)^2+(2\times w)^2+2\times a_n\times (2\times w)$

$\begin{aligned}=\sum_{i=1}^{i\le n} (a_i)^2+n(2\times w)^2+(\sum_{i=1}^{i\le n} 2\times a_i)\times (2\times w)\end{aligned}$

所以预处理出 $\begin{aligned}\sum_{i=1}^{i\le n} (a_i)^2\end{aligned}$ =sum1， $\begin{aligned}(\sum_{i=1}^{i\le n} 2\times a_i\end{aligned})$ =sum2 即可。

然后考虑二分 $w$ ，check 函数这样子写：

inline bool check(ll x){
    ll t=x*2;
    return sum1+t*t*n+sum2*t<=c;
}

代码

思路很简单，那么就直接给出代码吧qwq！

#include <bits/stdc++.h>
#define i128 __int128 //不开int128见祖宗
using namespace std;
i128 T,n,c,t,sum1,sum2; //sum1 sum2见上
template<typename T> inline void read(T& n){
    T x=0;bool f=1; //int128特有的快读快写（悲）
    char c=getchar();
    while(c<48||c>57)
        f=c!=45,c=getchar();
    while(c>47&&c<58)
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    n=f?x:-x;
}
template<typename T> void write(T x){
    if(x<0) putchar(45),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
inline bool check(i128 x){
    i128 t=x*2; //check，见上
    return sum1+t*t*n+sum2*t<=c;
}
int main(){
    ios::sync_with_stdio(0);
    read(T);
    while(T--){
        read(n),read(c),sum1=0,sum2=0;
        for(int i=1;i<=n;i++)
            read(t),sum1+=t*t,sum2+=2*t; //预处理
        i128 l=0,r=1e9,mid;
        while(l<=r){ //二分
            mid=l+r>>1;
            if(check(mid)) l=mid+1;
            else r=mid-1;
        }
        write(r),puts("");
    }
    return 0;
}

彩蛋

聊聊赛时的一场悲剧：

还剩最后22分钟时，跟 cyh 交流出了解法，她表示：我不想打了，感觉调不出来了。

但是本蒟蒻上次被 Skipped 的Div.4（5.6那次）可是做了 5 道，可不能成为耻辱，上次加了164Rating！

然后就开始调二分了，然而一直卡题，卡了7次到处改都是WA在Test4。

当时打的是：

#define ll __int128 //C++17,GCCmsys264能过
...
ll l=0,r=c,mid; //r太大了！！！，l=0用不着
while(l<r){ //PS：原版题解里的l<=r是怕玄学，实际上一样的
    mid=l+r>>1;
    if(check(mid)) l=mid+1;
    else r=mid;
}