二分
注意:在整数二分中,要遵循《数的范围》二分模板,不能l=mid和r=mid同时存在,如果是浮点数的话就可以参考《数的方根》
时间复杂度
O(N^2*logN)
参考文献
Java代码
class Sum implements Comparable<Sum>{//从小到大排序
int c;
int d;
int s;
public Sum(int c,int d,int s) {
this.c=c;
this.d=d;
this.s=s;
}
@Override
public int compareTo(Sum o) {
if(s!=o.s)return Integer.compare(s, o.s);//依次将总和、c、d小的放在前面
if(c!=o.c)return Integer.compare(c, o.c);
return Integer.compare(d, o.d);
}
}
public class _1221 {
private static Sum[] sums=new Sum[5000000];
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int i=0;
for(int c=0;c*c<=n;c++) {
for(int d=c;d*d+c*c<=n;d++) {
sums[i++]=new Sum(c, d, c*c+d*d);
}
}
Arrays.sort(sums,0,i);//只排序前i个
for(int a=0;a*a<=n;a++) {
for(int b=a;b*b+a*a<=n;b++) {//边界要这样搞,不然二分也过不了
int l=0,r=i-1;
while(l<r) {
int mid=l+r>>1;
if(a*a+b*b>=n-sums[mid].s)r=mid;
else l=mid+1;//是整数二分,所以要加一
}
if(a*a+b*b==n-sums[l].s) {
System.out.println(a+" "+b+" "+sums[l].c+" "+sums[l].d);
return;//退出循环,结束程序
}
}
}
}
}
哈希表
时间复杂度
$O(n^2)$
Java 代码
private static Map<Integer, Integer> map=new HashMap<Integer, Integer>();
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
for(int c=0;c*c<=n;c++) {
for(int d=c;c*c+d*d<=n;d++) {
if(!map.containsKey(c*c+d*d))//若哈希表中不存在的话,则存进去
map.put(c*c+d*d,c);
}
}
for(int a=0;a*a<=n;a++) {
for(int b=a;b*b+a*a<=n;b++) {
if(map.containsKey(n-a*a-b*b)) {
int c=map.get(n-a*a-b*b);
int d=(int)Math.sqrt(n-a*a-b*b-c*c);
System.out.println(a+" "+b+" "+c+" "+d);
return;
}
}
}
}
没有按字典序