题目：
1221. 四平方和 - AcWing题库
思路1：暴力
暴力枚举
1.枚举顺序为从a到c，依次增大。
2.t=n-a*a-b*b-c*c，求得d=sqrt(t)
3.判断求出的d是否成立。d要求：d*d==t&&d>=c
#include<iostream>
#include<cmath>
using namespace std;
const int N=2300;
int n,a,b,c,d;
int main()
{
cin>>n;
for(a=0;a*a<n;a++)
for(b=a;a*a+b*b<n;b++)
for(c=b;a*a+b*b+c*c<n;c++){
int t=n-a*a-b*b-c*c;
d=sqrt(t);
if(d*d==t&&d>=c){
cout<<a<<" "<<b<<" "<<c<<" "<<d;
return 0;
}
}
}思路2：二分
1.以空间换取时间的思路。先枚举c,d的情况，将所以可能存入结构体Sum中。再枚举a,b的情况。我们若对Sum.s进行从小打到的排序，就可以用二分寻找满足条件的Sum。
2.在枚举a,b的过程中寻找Sum，此时已经可以确定a,b满足字典序，为保证c,d也为字典序，我们需要对结构体进行自定义排序，不仅仅要按照Sum.s从小到大的顺序排序，同时还要兼顾Sum.c和Sum.d。因此，这里我们需要用到自定义排序或者减号运算符重载。
自定义排序：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 9 * 1e6;
int a, b, c, d, n, m;
struct Sum
{
int s;
int c;
int d;
}sum[N];
bool comp(struct Sum sum1,struct Sum sum2)//自定义输出
{
if (sum1.s != sum2.s)return sum1.s < sum2.s;
else if (sum1.c != sum2.c)return sum1.c < sum2.c;
else return sum1.d < sum2.d;
}
int main()
{
cin >> n;
//先枚举c,d，将平方和以及c,d存入结构体Sum(以空间换取时间)O(n3)->O(n2)
for (c = 0; c * c < n; c++)
for (d = c; c * c + d * d <= n; d++) {//存入结构体
sum[m].s = c * c + d * d;
sum[m].c = c;
sum[m].d = d;
m++;
}
sort(sum, sum + m, comp);//自定义输出（先后按照结构体内s,c,d从小到大顺序排序）
//枚举a、b,同时二分查找符合条件的c、d
for(a=0;a*a<n;a++)
for (b = a; a * a + b * b < n; b++) {
int L = 0, R = m-1;//对下标二分
int t = n - a * a - b * b;
while (L < R) {
int mid = L + R >> 1;
if (sum[mid].s >= t)R = mid;
else L = mid + 1;
}
if (sum[L].s == t) {
cout << a << " " << b << " " << sum[L].c << " " << sum[L].d;
return 0;
}
}
}减号运算符重载：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 9 * 1e6;
int a, b, c, d, n, m;
struct Sum
{
int s;
int c;
int d;
bool operator<(const Sum& t)const//重载减号运算符，实现自定义排序
{
//不同情况下减号赋予不同含义，返回值也不一样
if (s != t.s)return s < t.s;
else if (c != t.c)return c < t.c;
else return d < t.d;
}
}sum[N];
int main()
{
cin >> n;
//先枚举c,d，将平方和以及c,d存入结构体Sum(以空间换取时间)O(n3)->O(n2)
for (c = 0; c * c <= n; c++)
for (d = c; c * c + d * d <= n; d++) //存入结构体
sum[m++] = { c * c + d * d,c,d };//结构体与类不同，无需构造函数
sort(sum, sum + m);//自定义输出（先后按照结构体内s,c,d从小到大顺序排序）
//枚举a、b,同时二分查找符合条件的c、d
for (a = 0; a * a < n; a++)
for (b = a; a * a + b * b < n; b++) {
int L = 0, R = m - 1;//对下标二分
int t = n - a * a - b * b;
while (L < R) {
int mid = L + R >> 1;
if (sum[mid].s >= t)R = mid;
else L = mid + 1;
}
if (sum[L].s == t) {
cout << a << " " << b << " " << sum[L].c << " " << sum[L].d;
return 0;
}
}
}
