牛客-星际穿越

发表于 | 分类于 ，

题目

描述

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

输入

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

输出

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

Example

Input

10

Output

2

题解

二分法

  • 二分的范围为 [le,re], le=1, re=min(n,1E+9)
  • 若 中点 m,m 满足 m*m+m==n ,结束二分;
  • 若不满足,继续二分 直到 le>re 为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,now,le,re,m,tmp;

int main()
{
    while(cin>>n)
    {
        le=1,re=min(n,1000000000LL);
        while(le<=re)
        {
            m=m=(le+re)>>1;
            tmp=m*m+m;
            if(tmp==n) 
            {
                now=m;
                break;
            }
            if(tmp<n)
            {
                now=m;
                le=m+1;
            }
            else
                re=m-1;
        }
        cout<<now<<endl;
    }
}

函数法

  • 假设发射消耗 x,则 x+x*x <= n;
  • 一元二次不等式求解得 x <= (-1+sqrt(1+4n))/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,now,le,re,m,tmp;

int main()
{
    while(cin>>n)
    {
        cout<<(int)(-1+sqrt(1+4*n))/2<<endl;
    }
}