蒟蒻解法——纯暴力 O(n²)

_LiM @ 2017-10-02 10:57:21

#include<iostream>
#include<cmath>
using namespace std;
int i,n,sum,j,ans; 
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)     //用一个双循环 模拟
        {
            sum+=i;
            ans++;
            if(ans==n)
            {
                cout<<sum;
                return 0;//这里如果发现已到次数，直接return 0，不用break
            }
        }
    }    
}
dalao们说还有哪些地方可以简写？

by _LiM @ 2017-10-02 10:58:15

一遍AC

by iphone_X @ 2017-10-03 15:06:05

有，你的双循环的时间复杂度较长，这题就是几个数的平方累加，你再在最后判一下有没有超过N，代码如下（也是一遍过）：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int a,b,n,m,i=0;
int main()
{
    cin>>n;
    while(n>0){
        i++;
        if(n>i){    //判断有无超N
            m+=i*i;
            n-=i;
        }
        else{
            m+=i*n;
            n-=n;
        }
    }
    cout<<m;
    return 0;
}
这样耗时就可以缩短

by iphone_X @ 2017-10-03 15:06:39

@李鸣宇

by _LiM @ 2017-10-03 15:39:37

谢谢 [/fly]O(∩_∩)O谢谢[/fly]

by MscWood @ 2017-10-18 20:45:21

@_hutao_

代码优化：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    long long ans=0,k,i=1;
    cin>>k;
    while(k>=i)
    {
        k-=i;
        ans+=i*i;
        i++;
    }
    ans+=k*i;
    cout<<ans;
    return 0;
}

by pascalfans @ 2018-06-24 15:02:54

@hutao

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
 inc i,n,x,y,s;
 cin>>n;
 y=1;
 x=1;
 s=0;
 for(i=1;i<=n;i++)
  {
   s+=y;
   x--;
   if (x=0){
            x=y+1;
            y+=1;
           }
  }
 cout<<s;
 return 0;
 }

by hutao @ 2018-07-16 17:17:24

@pascalfans 怎么了

by pascalfans @ 2018-07-19 15:30:27

@错了

（诶呀）