输入样例：
5
输出样例：
0 0 1 2本题思路：以空间换时间
由于暴力解法我们至少要枚举三个数，然后计算出第四个数
呢么需要进行三重循环,时间复杂度大概为O(n3),则会超时
所以我们要进行优化来降低时间复杂度
我们的思路是：
将三重循环，拆解成两次二重循环
在第一次循环中，先计算c^2+d^2,然后记录下结果和此时的c,d的值
在第二次循环中，可以直接通过遍历a,b,查找t(t=n-a^2-b^2)
找到的第一组满足a^2+b^2+c^2+d^2=n,的便是字典序最小的，直接输出即可
最重要的怎样存储c^2+d^2？
可以考虑哈希表,也可以使用结构体数组+二分
哈希表（unordered_map现在数据加强了过不了，但是可以模拟哈希表）
#include<iostream>
#include<algorithm>
#include<cstring>//memset赋值的头文件
#include<cmath>//使用了sqrt开根号函数
using namespace std;
// typedef pair<int,int> PII;
const int N=5e6+10;int n;
int r[N];
// c有根号N种可能，d也是所以组合起来，是2*根号N种<N
int main()
{cin>>n;memset(r,-1,sizeof r);//先将其附一个特殊值，也就是题目不会出现的值//由于a,c,b,d 肯定是>=0for(int c=0;c*c<=n;c++){for(int d=c;c*c+d*d<=n;d++)//为了按字典序输出确保c<b{int t=c*c+d*d;if(r[t]==-1)//由于要求字典序最小，所以保留的是最先出现的值，如果之前赋值过则不需要再进行赋值{r[t]=c;}}}for(int a=0;a*a<=n;a++){for(int b=a;a*a+b*b<=n;b++){int t=n-a*a-b*b;if(r[t]==-1)//说明没有这组解continue;int c=r[t];int d=sqrt(t-c*c);//sqrt开根号的意思cout<<a<<' '<<b<<' '<<c<<' '<<d;return 0;}}return 0;
}
结构体数组+二分
#include<iostream>
#include<algorithm>//sort排序函数的头文件
using namespace std;
const int N=5e6+10;
struct Sum{int s,c,d;bool operator < (const Sum &t) const//重载<原因是应为，为了保证字典序{if(s !=t.s) return s < t.s;//如果这个s(c*c+d*d)之前出现过则就比较c和dif(c !=t.c) return c < t.c;//在s相同时,保证c最小return d<t.d;//在s和c相同时,保证d最小}
};int n;
Sum r[N];int main()
{cin>>n;int k=0;for(int c=0;c*c<=n;c++){for(int d=c;c*c+d*d<=n;d++){r[k++]={c*c+d*d,c,d};//{s,c,d},对应的}}sort(r,r + k);//使用的是重载的<号for(int a=0;a*a<=n;a++){for(int b=a;a*a+b*b<=n;b++){int t=n-(a*a+b*b);//找到t，由于里面也会有多个值为t但是我们要找到第一个，所以相当于找右条件（最小的大于等于t）的左边界int L=0,R=k-1;while(L<R){int mid=L+R>>1;if(r[mid].s>=t) R=mid;else L=mid+1;}if(r[R].s==t)//如果找到，就直接输出{cout<<a<<' '<<b<<' '<<r[R].c<<' '<<r[R].d;return 0;}}}return 0;
}
