首页 > 试题广场 >

星际穿越

[编程题]星际穿越

热度指数：43461 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

航天飞行器是一种复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x² 程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？

数据范围： $1 \le h \le 10^{18} \$

输入描述:

每个输入包含一个测试用例。每个测试用例包含一行一个整数 h （1 <= h <= 10^18）。

输出描述:

输出一行一个整数表示结果。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

C/C++

骏博日博的迷弟

水题水题

#include <cstdio>
#include <cmath>

int main()
{
	long long h;
	while (scanf("%lld", &h) != EOF)
	{
		double ans = (sqrt(4.0*h + 1) - 1)/2;
		printf("%d\n", int(ans));
	}
	return 0;
}

发表于 2017-08-07 19:05:30 回复(9)

dragonhaw

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            long num = in.nextLong();
            long x = (long)Math.pow(num, 0.5);
            if(x * (x + 1) > num) {
                System.out.println(x - 1);
            } else {
                System.out.println(x);
            }
        }
    }
}

发表于 2017-08-14 20:48:16 回复(1)

Python

Benjaminz

print int(((1+4*input())**0.5-1)/2)

发表于 2017-08-11 16:09:41 回复(1)

schuman

#include<iostream>
#include<math.h>
using namespace std;
int main(){
    long i, h;
    while(cin >> h){
        long sqr = sqrt(h);
        for(i = sqr; i+i*i > h; i--){}
        cout << i << endl;;
    }
    return 0;
}

发表于 2016-08-12 15:37:09 回复(4)

ACpeppermint

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    long long h;
    cin >> h;
    cout << (int)floor( ( sqrt((double)(1 + 4 * h)) - 1 ) / 2 ) << endl;
    return 0;
}

编辑于 2018-10-12 01:45:55 回复(0)

Python

yzdeng

h=int(input())
print(int((h+0.25)**0.5-0.5))

发表于 2018-05-16 18:50:18 回复(0)

stubsx

解方程后向下取整即可


	#include <iostream>



	#include <cmath>



	using namespace std;



	





	int main(int argc, const char * argv[]) {



	    double h,x;



	    int answer;



	    cin>>h;



	    x=sqrt(h+0.25)-0.5;



	    answer=floor(x);



	    cout<<answer<<endl;



	    return 0;



	}

发表于 2018-01-30 11:03:00 回复(0)

wangwenbin

// 直接解方程
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long n = sc.nextLong();
            long k = (int)Math.sqrt(n);
            if(k*(k+1)<=n){
                System.out.println(k);
            }else{
                System.out.println(k-1);
            }
        }
    }
}

发表于 2017-08-18 18:55:50 回复(1)

Java

pein531

二分搜索

设损耗为x，我们要求的就是能满足x*(x+1)<=h的最大x，x的搜索空间为 $[0,\sqrt{h} +1]$ 。

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);
    }
}

编辑于 2022-01-08 12:10:29 回复(0)

金金金m

/*直接使用求根公式计算 然后转化为int即可*/

#include <bits/stdc++.h>

using namespace std;
int main()
{
long long h;
cin>>h;
cout<<(int)(-0.5+sqrt(1+4*h)*0.5);
}

编辑于 2019-04-21 14:52:35 回复(0)

Java

jade_liu_123

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);
    }
}

编辑于 2018-11-02 19:04:03 回复(0)

🚶201804281411308

简单的n^2+n<=h  一直h求n的最大值  ---->n<=((4h+1)开根号-1)/2
public class Program4 { public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);  long a=scanner.nextLong();  System.out.println(((long)Math.sqrt(4*a+1)-1)/2);  }
}

发表于 2018-09-12 20:53:19 回复(1)

Java

牛客4937605号

/*没有用库函数，二分查找，一个技巧就是通过位数快速压缩第一次查找的区间*/
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);  }
}

编辑于 2018-08-25 00:12:26 回复(0)

YY-帆S

<?php
$h = trim(fgets(STDIN));
//计算 x²+x<=10 即 （x+1/2）²-1/4-$h<=0  即 x<=根号（h+0.25）-1/2
echo floor(sqrt($h+0.25)-0.5);

发表于 2018-07-23 21:57:52 回复(0)

牵着蜗牛

/*
    直接对h求算术平方根向下取整
   需要注意的是定义h变量要用long,如果使用int会超出范围
*/
import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        long h=sc.nextLong();
        test(h);

    }
    public static void test(long h){
        long a=(long)Math.floor(Math.sqrt(h));
        for(long i=a;i>=0;i--){
            if((i*i+i)<=h){
                System.out.println(i);
                break;
            }
        }
    }
}

发表于 2018-06-11 21:10:37 回复(0)

C.A.Y.P

#include<stdio.h>
#include<math.h>
int main(){
   unsigned long h ;
     double result;
   double re;
   unsigned long resultint;
    scanf("%ld",&h);
    result = sqrt((double)h);
   resultint = (int)result;
    re = result - resultint;
    if(re<0.419){
      resultint--;
   }
    if(h==2){
     resultint = 1;
    }
   printf("%ld",resultint);
}

发表于 2018-03-05 15:41:00 回复(0)

风一样的男子hm

哎，这题好烦，就拿精度说事儿

大家注意一下定义的平方根的值和输入的值要定义成long类型的，就ok了。

发表于 2018-01-31 15:40:37 回复(0)

Jason_liu


	import java.util.Scanner;



	





	public class Interstellar {



	





	    public static void main(String[] args) {



	        Scanner sc=new Scanner(System.in);



	        while(sc.hasNext()) {



	            long m=sc.nextLong();



	            for(long i=(long) Math.floor(Math.sqrt(m))-1;i<=Math.pow(10, 9);i++) {



	                if(i*(i+1)>m) {



	                    System.out.println(i-1);



	                    break;



	                }



	            }



	        }



	        sc.close();



	    }



	}

发表于 2018-01-23 09:48:05 回复(0)

C/C++

nbgao

#include <iostream>
#include <cmath>
using namespace std;

int main()
{     long long h;     cin>>h;     long long x = (int)sqrt(h);     while(x*(x+1)<=h)     {         x++;     }     cout<<x-1<<endl;     return 0;
}

发表于 2018-01-19 00:31:43 回复(0)

讲道理的牛肉丸顶呱呱

#include <iostream>
#include <math.h>
using namespace std;
int main()
 {
     long long h;
     cin>>h;
     long long temp=(sqrt(1+4*h)-1)/2;
    int result=temp;
    cout<<result<<endl;
    return 0;
 }

发表于 2017-12-17 15:35:56 回复(0)

提交观点

问题信息

二分基础数学数学

来自：网易2017内推笔试编...

难度：

181条回答 80收藏 20030浏览

通过挑战的用户

查看代码

牛客74315...

2022-09-15 21:52:41
努力找一个好工...

2022-09-09 21:09:37
Gop4

2022-09-08 16:19:45
牛客58227...

2022-09-08 08:43:26
牛客31245...

2022-09-06 16:23:20

星际穿越

输入描述:

输出描述:

输入

输出

输入

输出

二分搜索

问题信息

热门推荐

通过挑战的用户

相关试题