C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2500010;
int n,m;
struct Sum{
int s,c,d;
bool operator<(const Sum &t) const{
if(s!=t.s) return s<t.s;
if(c!=t.c) return c<t.c;
else return d<t.d;
}
}sum[N];
int main(){
cin>>n;
for(int c=0;c*c<=n;c++)
for(int d=c;c*c+d*d<=n;d++)
sum[m++]={c*c+d*d,c,d};
sort(sum,sum+m);
for(int a=0;a*a<=n;a++)
for(int b=0;a*a+b*b<=n;b++){
int t=n-a*a-b*b;
int l=0,r=m-1;
while(l<r){
int mid = l + r >> 1;
if (sum[mid].s>=t) r = mid;
else l=mid+1 ;
}
if(t==sum[l].s)
{
printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
return 0;
}
}
return 0;
}
为何用r=mid这个模版,首先我们知道两个模版的区别在于向上或者向下取整以来防止死循环,而在这个题目中向上取整和向下取整这两个因素会影响到我们的最终答案。题目要求输出的答案必须是字典序最小,而有些输入存在多个答案并且他们是相邻的,例如100存在两个符合解,第一个为0 0 0 10;第二个为0 0 6 8 而sum数组中存入的是c和d ;而sum数组中存入的是c和d,由于我们先枚举了a和b
所以a和b的字典序一定是最小的,这个时候我们只需要考虑c和d的字典序,像100当我们二分时,我们最后一次二分是0 10和6 8之间,二者的下标相差1,更新mid=l+r+1>>1的话,mid向上取整,并且6 8也是符合最后的判断条件,这样就导致了错误解。所以只能用向下取整的模版。也就是说如果求的是字典序最大的解就必须用向上取整的模版。
个人看法,如果用什么不对,大佬们多多纠正