星际穿越

二分搜索

设损耗为x，我们要求的就是能满足x*(x+1)<=h的最大x，x的搜索空间为。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long h = Long.parseLong(br.readLine());
        long left = 0, right = (long)Math.sqrt(h) + 1, x = 0;
        while(left < right){
            long mid = left + ((right - left) >> 1);
            if(mid * (mid + 1) > h){
                right = mid - 1;
            }else{
                x = mid;
                left = mid + 1;
            }
        }
        System.out.println(x);
    }
}

import java.util.*;
public class Main{
     public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        Long durability = cin.nextLong();
        // x+x*x<durability
        Long sqrt = (long) Math.sqrt(durability);
        while (sqrt > 0) {
            if ((sqrt + 1) * sqrt > durability) {
                sqrt -= 1;
            }
            break;
        }
        System.out.println(sqrt);
       
    }
}

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    /**
    *这一题就是考察最接近h的sum （=X + X * X）；
    *限制h最大为10^18，我们知道int约为2*10^9，long是9*10^18，所以我们的数据类型为long
    *使用sqrt就可以了，开方取整，如果取整后（X + X * X）恰等于h，那么就取X，否则我们就取小于X的一位就可以了，
    *因为 （a - 1）^2 = a^2 - 2*a + 1 < a^2 - a < a^2 < a^a + a
    *a减一已经能够让出一个a了
    */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long num = Long.parseLong(br.readLine().trim());
        long numSqrt = (long)Math.sqrt(num);
        long tolerance = (numSqrt + 1) * numSqrt <= num ? numSqrt : (numSqrt -1);
        System.out.println(tolerance);
    }
}

/*没有用库函数，二分查找，一个技巧就是通过位数快速压缩第一次查找的区间*/
import java.util.Scanner;
public class Main{  // 寻找最大的x整数解使得x(x+1)<=h  public static void main(String[] args) {  // 考虑一个2位数，最大为99，则99*100=9900，最多也到不了5位数  // 因此，当h为k位数时，x的位数不会超过(k+1)/2，但是也不会低于(k+1)/2-1  Scanner scanner = new Scanner(System.in);  long h = scanner.nextLong();
        scanner.close();
        if(h<2){
            System.out.println(0);
            return;
        }
        String hString = String.valueOf(h);    int bit = hString.length();    int maxbit = (bit + 1) / 2, minbit = maxbit - 1;    long left = (long) Math.pow(10, minbit), right = (long) Math.pow(10,  maxbit + 1);  long mid=(left+right)/2;  while(left<right){    long pivot=mid*(mid+1);    if(pivot>h){    right=mid;    mid=(left+right)/2;    }else{    long newpivot=(mid+1)*(mid+2);    if(newpivot>h)    break;    left=mid;    mid=(left+right)/2;    }    }    System.out.println(mid);  }
}

这题目有点水吧 

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        long h = Long.parseLong(line);
        System.out.println(max(h));
    }
    public static long max(long h) {
        for (long i = (long) Math.pow(h, 0.5); i >= 1; i --) {
            if (i * (i + 1) <= h) {
                return i;
            }
        }
        return 0;
    }

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            long limit = in.nextLong();
            int res = (int)(Math.sqrt(1+4*limit) - 1) / 2;
            System.out.println(res);
        }
    }
}

//本题我解的可能有点复杂，是用了二分查找法来做。并且考虑了数值大于long型的情况

    public static void main(String [] args){

        Scanner in = new Scanner(System.in);
        String s = in.next();
        BigInteger bi = new BigInteger(s);

        BigInteger CONSTANT_1 = new BigInteger("1");
        BigInteger CONSTANT_2 = new BigInteger("2");
        BigInteger X = new BigInteger("0");
        BigInteger left = X;
        BigInteger right = bi;
        BigInteger res = X;
        while (left.compareTo(right) == -1 || left.compareTo(right) == 0){
            BigInteger mid = left.add(right).divide(CONSTANT_2);
            BigInteger temp = mid.multiply(mid.add(CONSTANT_1));
            if (temp.compareTo(bi) == -1){
                if (mid.add(CONSTANT_1).multiply(mid.add(CONSTANT_2)).compareTo(bi)==1){
                    res = mid;
                    break;
                }else {
                    left = mid.add(CONSTANT_1);
                }
            }else if (temp.compareTo(bi)==1){
                right = mid.subtract(CONSTANT_1);
            }else {
                res = mid;
                break;
            }
        }
        System.out.println(res);

    } 

import java.util.*;
public class Main
    {
    public static void main(String[] args)
        {
         Scanner sc = new Scanner(System.in);
	    	 long  h=0;
	         while(sc.hasNext())
	 	       {
	 	         h=sc.nextLong();
	 	         long i=(long) Math.sqrt(h);
	 	         for(;i>=0;i--)
	 	             {
	 	             if((i+i*i)<=h)
	 	             {
	 	            	 System.out.println(i);
	 	            	 break;//48,9104k
	 	             }
	 	         }
	 	       } 
    }
}