航天飞行器是一种复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x2 程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？
数据范围：
[编程题]星际穿越
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long h = in.nextLong();
long i = 0;
for(i = 0; i * i <= h; i++){
if(i * i + i <= h && (i + 1) * (i + 1) + i + 1 > h){
System.out.println(i);
return;
}
}
System.out.println(-1);
}
}
发表于 2024-10-08 12:23:25
回复(0)
二分搜索
设损耗为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);
}
}
编辑于 2022-01-08 12:10:29
回复(0)
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);
}
}
发表于 2021-09-09 21:54:22
回复(0)
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)
关键的一步：long x = (long)Math.sqrt(n);
要是从1开始判断，估计超时的时间是中国和美国的时差，要一步到位，定位到离所求数最近的位置
实现如下：
import java.util.Scanner;
public class Main{public static void main(String[] args){
Main t = new Main();
Scanner in = new Scanner(System.in);
while(in.hasNext()){
long h = in.nextLong();
t.get(h);
}
}
public void get(long n){
long x = (long)Math.sqrt(n);
while(x>0){
if(x*x+x<=n){
System.out.println(x);
return;
}
x--;
}
System.out.println(0);
}
}
发表于 2018-08-26 21:14:44
回复(0)
/*没有用库函数，二分查找，一个技巧就是通过位数快速压缩第一次查找的区间*/
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)
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;
}
发表于 2018-05-19 16:37:56
回复(0)
import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { long h = Long.parseLong(scanner.nextLine()); double x = (Math.sqrt(4 * h + 1) - 1) / 2; System.out.printf("%.0f", Math.floor(x)); } } }就是解方程：x^2 + x <= h，是一个开口向上的抛物线，求抛物线与x轴的正交点，就是(-b+sqrt（b^2-4ac))/2a，直接带公式就行，唯一需要注意的是h的范围，h要定义为一个long型而不是int型
发表于 2017-11-29 20:14:01
回复(0)
//本题我解的可能有点复杂，是用了二分查找法来做。并且考虑了数值大于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);
}
发表于 2017-11-14 15:00:10
回复(0)
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
}
}
}
}
}
发表于 2017-08-09 16:27:54
回复(3)
问题信息
通过挑战的用户
查看代码-
2022-09-15 21:52:41
-
2022-09-09 21:09:37
-
2022-09-08 16:19:45
-
2022-09-08 08:43:26
-
2022-09-06 16:23:20
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
