526互联

ABC330 C Minimize Abs 2 题解

发布时间 2023-11-27 20:56:20作者: Martian148

Link

ABC330 C Minimize Abs 2

Question

给定一个整数 D

求 \(|x^2+y^2-D|\) 的最小值，\(x,y\) 为非负整数

Solution

同时枚举 \(x,y\) 显然是不切实际的，考虑折半枚举

枚举 \(x^2\) 然后寻找接近 \(D-x^2\) 的平方值，可以使用二分，或者需处理出 \(y^2\) 用双指针跑，前后扰动一个判断

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+5;
LL a[maxn],tot,ans=2e12+10;
int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    LL D;
    cin>>D;
    for(LL i=0;i*i<=D;i++)
        a[++tot]=i*i;
    LL pos=tot;
    for(int i=1;i<=tot;i++){ //D-(x2+y2)
        while(pos>0&&a[pos]+a[i]>D) pos--;
        if(pos<tot) ans=min(ans,a[pos+1]+a[i]-D);
        if(pos>0) ans=min(ans,D-(a[pos]+a[i]));
    }
    printf("%lld\n",ans);
    return 0;
}