首页 > 试题广场 >

疯狂序列

[编程题]疯狂序列
  • 热度指数：4811 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
东东从京京那里了解到有一个无限长的数字序列: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...(数字k在该序列中正好出现k次)。东东想知道这个数字序列的第n项是多少,你能帮帮他么

输入描述:
输入包括一个整数n(1 ≤ n ≤ 10^18)


输出描述:
输出一个整数,即数字序列的第n项
示例1

输入

169

输出

18
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    long n;
    scanf("%ld", &n);
    long a=1, b=1, c=-2*n, s;
    s = ceil((-b+sqrt(b*b-4*a*c))/(2*a));
    printf("%ld\n", s);
    return 0;
}

发表于 2020-10-06 00:34:03 回复(0)
更多回答
Cambell头像 Cambell
import math

n = int(input())
f = -0.5+0.5*math.sqrt(1+8*n)
print(math.ceil(f))

思路：
1 22 333 ...
1  2   3 ... 
相当于求 1+2+3+...+x >= n 时x的最小值，由等差数列求和公式得：
(1+x)x/2 >= n 得：f(x):x^2+x-2n >= 0
又因为函数对称轴为-1/2，因此求f(x)右侧根再取上界即可



发表于 2019-04-11 11:38:40 回复(0)
pein531头像 pein531
这道题可以直接用循环求和的方式求解，时间复杂度为O(n)，从num=1开始，num每自增一次，项数都增加num个，直到项数超过n，然后输出此时的num即可。 
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 n = Long.parseLong(br.readLine().trim());
        long calNum = 0, start = 1;
        while(calNum < n){
            calNum += start;
            start ++;
        }
        System.out.println(start - 1);
    }
}
更快地，这道题还可以用数学方法求解，时间复杂度O(1)，我们可以很容易发现，1有1项，2有2项，3有3项，...，k有k项，根据高斯求和公式，只需判断什么时候k*(k+1)/2>=n即可。 
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 n = Long.parseLong(br.readLine());
        long k = (long)Math.sqrt(n<<1);
        if(k*(k + 1) >= n<<1)
            System.out.println(k);
        else
            System.out.println(k + 1);
    }
}



发表于 2021-02-23 10:52:18 回复(0)
hzpzlz1314头像 hzpzlz1314 
//AC代码
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    long long int n;
    cin>>n;
    long long int num;
    long double x = sqrt(2*n+1/4)-1.0/2;
    num = x+1;
    cout<<num<<endl;
    return 0;
}
求解二元一次方程：n<=(x+1)*x/2，result = x+1
发表于 2019-04-11 09:54:25 回复(1)
C/C++
专业菜鸟i头像 专业菜鸟i 
// 暴力梭哈        菜鸟出品。
#include<stdio.h>
int main(){
    long n,nn,i;
    scanf("%ld",&n);
    nn=n;
    for(i=1;i<nn;i++){
        n-=i;
        if(n<1){
            printf("%d",i);
            break;
        }
    }
    return 0;
}
发表于 2019-03-07 20:55:30 回复(1)
C/C++
yvettre头像 yvettre

等差数列求和sum=1+2+3+...+i=i(i+1)/2就是排完i之后数列中拥有元素的个数，如果n大于i(i+1)/2而又小于等于(i+1)(i+2)/2，那么答案肯定是i+1，所以以此实现了helper1函数，也当然是对过大的n会超时啦。

然后假设n=i(i+1)/2，那么答案就是i，也就是i约等于sqrt(2n)。对于n=i(i+1)/2，i肯定是等于sqrt(2n)向下取整，但是如果n>i(i+1)/2，答案就可能是sqrt(2n)向下取整或向上取整了。。想了想，其实结合helper1就OK了，即：先用i=floor(sqrt(2n))求得一个最接近答案的i，然后如果i(i+1)/2大于n，那么答案就是i；否则答案是i+1。

最终实现helper2函数：

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

void helper1(long long n){
    // 只能90%通过，最后一个超时，意料之中
    long long i=1;
    long long sum=0;
    while(n>sum){
        sum = (i*(i+1))>>1;
        i++;
    }
    cout<<i-1;
}

void helper2(long long n){
    double res = sqrt(double(n<<1));
    long long small = floor(res);
    if (((small*(small+1))>>1)<n) cout<< small+1;
    else cout<<small;
    //long long small = floor(res);
    //long long big = ceil(res);
    //if (res-small>big-res) cout<<big;
    //else cout<<small;
}

int main(){
    long long n;
    while(cin>>n){
        helper2(n);
    }
}

不过，其实当n越大，答案就越不容易出错。。严谨的证明我还是智商有限。。所以helper2中那段注释掉的代码虽然能通过所有样例。。但看看就好=。=

发表于 2019-02-17 21:17:10 回复(0)
向宇回桌头像 向宇回桌

OEIS大法好 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long num = sc.nextLong();
        long ans = (int)Math.ceil(((-1 + Math.sqrt(1+8*num)) / 2));
        System.out.println(ans);
        return;
    }
}
编辑于 2019-01-27 18:17:44 回复(0)
笨蛋蜘蛛头像 笨蛋蜘蛛 
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
        long n = sc.nextLong();
        int i;
        for( i=0;n>0;i++)
            n-=i;
        System.out.println(i-1);
    }
    sc.close();
}
}
发表于 2019-03-26 11:23:19 回复(1)
Python
牛客122691762号头像 牛客122691762号 
n=int(input())
x=(2*n+0.25)**0.5+0.5
print(int(x) if int(x)-x!=0 else int(x)-1)

发表于 2021-02-14 15:54:46 回复(0)
何处理红绡丶头像 何处理红绡丶 
package com.qiye;

import java.util.Scanner;

public class CrazySequence {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong();
        long i= 1;
        long sum = 0;
        while (true){
            if(x <= sum){
                break;
            }
            sum += i;
            i ++;
        }
        System.out.println(i - 1);
    }
}

发表于 2020-03-28 18:02:07 回复(0)
牛客694917813号头像 牛客694917813号
提供简单的C语言解法，其实就是简单的等差数列求和，我们利用k(1+k)/2 = n求出根的值，这里面有一个技巧放缩就是sqrt(8)*sqrt(n) = sqrt(8*n)<sqrt(8*n + 1),但是没关系，咱们最后补加1就行（不能直接sqrt(8*n + 1)，因为当n = 2*10^18次方的时候会溢出，所以只能分开求）
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

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

发表于 2020-03-17 15:47:57 回复(0)
嘎嘎嘎~头像 嘎嘎嘎~ 
 //等差数列不等式
import java.util.*;
public class Main{
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            Cal(sc);
        }
    }
    public static void Cal(Scanner sc){
        long n=sc.nextLong();
        long sum=0;
        for (long i=1;i<=n;i++){
             if(i*i+i>2*n && (i-1)*(i-1)+i-1<2*n){
                 System.out.println(i);
                 return ;
             }
            if(i*i+i>2*n ){
                 System.out.println(i-1);
                 return ;
             }
        }
    }
}

发表于 2019-07-06 16:48:27 回复(0)
Java
张逐流头像 张逐流 
从1向上遍历结果会超时，可以用中学二次方程的公式解出，再向上取整即可。
import java.util.Scanner;
import java.lang.Math;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long l=sc.nextLong();
        long result=(long) Math.ceil((Math.sqrt(8*l+1)-1)/2);
        
        System.out.print(result);
    }
}

发表于 2019-06-22 14:58:56 回复(0)
Smart_Maggie头像 Smart_Maggie
#include<iostream>
using namespace std;
int main()
{
    long long n;//n的范围超过了int能表示的范围，所以使用long long类型
    cin >> n;
    int count = 0;
    for(long long i=1;n>i;i++)
    {
        n = n - i;
        count++;
    }
    cout << count+1 << endl;
    return 0;
}
发表于 2019-05-06 20:29:33 回复(0)
Python
徐付翠头像 徐付翠
输入描述:
输入包括一个整数n(1 ≤ n ≤ 10^18)
输出描述:
输出一个整数,即数字序列的第n项

没读懂题目什么意思，怎么就扯到等差序列上了？（输入是一个n，输出第n项，所以输出跟输入到底什么关系啊，这个输入的n是序列的什么东西啊）
编辑于 2019-04-28 11:02:43 回复(0)
陈陈201903181647449头像 陈陈201903181647449 
//i从1开始循环试探，当 i*(i+1)/2 >= input 的时候，说明此时的 i 已经到达输入的
//序列数，即此时的i为此输入对应值，然而算法复杂度过大；
//  经分析：i*(i+1)/2 <= (i+1)*(i+1)/2 ,而i+1 < Math.sqrt(input*2)情况下，
//i*(i+1)/2 < (i+1)*(i+1)/2 < input,不可能满足if条件
//无需该部分多余计算，故从Math.sqrt（input*2）开始循环，降低了计算复杂度

var input = parseInt(readline()),
    start = parseInt(Math.sqrt(input*2))

for(var i=start;;i++){
    if(input <= i*(i+1)/2){
        console.log(i)
        break
    }
}

编辑于 2019-04-13 16:05:38 回复(0)
大黄人头像 大黄人
import math
m = int(input())
n = int(math.sqrt(2*m))
if 2*m <= n*(n+1):
    print(n)
else:
    print(n+1)

发表于 2019-04-12 17:14:43 回复(0)
Python
兰偷荀令香头像 兰偷荀令香
等差数列
import math
n = int(input())
result = int(math.sqrt(n * 2))
if (result + 1) * result * (1 / 2) < n:
    print(result + 1)
else:
    print(result)
发表于 2019-04-10 10:43:40 回复(0)
Python
offer疯狂砸我吧头像 offer疯狂砸我吧 
#用等差数列求和的方法确定n在哪一个区间范围。
class Solution:
    n=int(input())
    ans=0
    t=int((2*n)**(0.5))
    for i in range(t-1,t+1):
        if i*(i+1)/2<=n and (i+1)*(i+2)/2>n:
            if i*(i+1)/2<n:
                ans=i+1
            else:
                ans=i
            break
    print ans

发表于 2019-03-30 18:21:11 回复(2)
Python
小小cx猿头像 小小cx猿 
#等差数列求和公式
import math
while(True):
    try:
        n = int(input())
        temp = int(math.sqrt(2*n)) + 1
        while(temp>=1):
            if(temp * (temp + 1) == 2 * n):
                ans = temp
                break
            if((temp - 1) * temp < 2 * n and temp * (temp + 1) > 2 * n):
                ans = temp
                break
            temp -= 1
        print(ans)
    except:
        break

发表于 2019-03-27 14:29:15 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 京东 2018 PHP工程师 数学 Java工程师
上传者：小小
难度：
22条回答 4106浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号