题目描述

blablabla

算法思想

1.从d开始逐一二分，但是可能导致最后的结果是多余4的,所以该方法不可行，只可以通过三个数据

package 蓝桥;

import java.util.ArrayList;
import java.util.Scanner;

public class 四平方和1 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt();
       int l=0;
       int tem=n;
       int r=n;
       int res=0;
       int a=0,b=0,c=0,d=0;
       ArrayList<Integer> alArrayList= new ArrayList<Integer>();
      while(res <n){
             while(l<r){
                 int mid=l+r+1 >>1;
                 long k=mid*mid;
                 if(k > tem) r=mid-1;
                 else{
                     l=mid;
                 }
             }
             if(l*l==n){
                 alArrayList.add(r);
                 break;
             }
             else if(l*l >n)r--;
             else{
                 alArrayList.add(r);
                 res+=l*l;
                 r=n-res;
                 l=0;
                 tem=r;
             }


       }
      int len=alArrayList.size();
      for(int i=len;i<4;i++){
          System.out.print("0 ");
      }
      for(int i=alArrayList.size()-1;i>=0;i--) System.out.print(alArrayList.get(i)+" ");
    }

}

2.枚举cc+dd的值，在和aa+bb的值进行比较
map的做法，map的做法需要在枚举每一个数字的时候加上限制，比如说枚举a的时候，aa4<=n,因为abcd的值可能都是a

package 蓝桥;

import java.util.HashMap;
import java.util.Scanner;

public class 四平方和2 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();

       HashMap<Integer, Integer> alHashMap=new HashMap<Integer, Integer>();
       for(int i=0;i*i*2<=n;i++){
           for(int j=i;(i*i+j*j)<=n;j++){
               int k=i*i+j*j;
               if(!alHashMap.containsKey(k)) alHashMap.put(k, i);
           }
       }
       for(int i=0;i*i*4<=n;i++){
           for(int j=i;(j*j+i*i)*2<=n;j++){
               int k=i*i+j*j;
               int kk=n-k;
               if(alHashMap.containsKey(kk)){
                   int c=alHashMap.get(kk);
                   int d=(int) Math.sqrt(kk-c*c);
                   System.out.println(i+" "+j+" "+c+" "+d);
                   return;
               }
           }
       }

    }

}

二分，数据加强了，还是过不去hhh

package 蓝桥;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class scd implements Comparable<scd>{
    int s;
    int c;
    int d;
    public scd(int s, int c, int d) {
        super();
        this.s = s;
        this.c = c;
        this.d = d;
    }
    @Override
    public int compareTo(scd o) {
        // TODO Auto-generated method stub
         if(s!=o.s)return this.s>o.s?1:-1;//依次将总和、c、d小的放在前面
            if(c!=o.c)return this.c>o.c?1:-1;
            return this.d>o.d?1:-1;
    }


}



 public class 四平方和3 {


    static int N=2500010;
    static scd scds[]=new scd [N];


    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
         BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
         int n=Integer.parseInt(bufferedReader.readLine());
         BufferedWriter bufferedWriter =new BufferedWriter(new OutputStreamWriter(System.out));
         int k=0;

         for(int i=0;i*i*2<=n;i++){
             for(int j=i;i*i+j*j<=n;j++){
                 scds[k++]=new scd(i*i+j*j, i, j);
             }
         }

         Arrays.sort(scds,0,k);
         for(int i=0;i*i*4<=n;i++){
             for(int j=0;(i*i+j*j)*2<=n;j++){
                 int s1=n-i*i-j*j;
                 int l=0;
                 int r=k-1;
                 while(l<r){
                     int mid=l+r>>1;
                     if(scds[mid].s<s1) l=mid+1;
                     else {
                        r=mid;
                    }
                 }
                 if(scds[l].s==s1){
                     bufferedWriter.write(i+" "+j+" "+scds[l].c+" "+scds[l].d);
                     bufferedWriter.flush();
                     bufferedWriter.close();
                     return ;
                 }
             }
         }
    }

}