数列问题

理想分数100，实际分数100

题目描述

思路：

首先看到都是输入一个数，输出一个数，让后再看到这个数据范围：1<=t<=1e4,1<=n<=1e9，这数据范围，O(tn),O(n+t),的算法都否认了，并且如果用数组来存储，一定会炸。于是就想到了推一下规律。我先打了一个dfs，将1-30的答案都搜了一遍，发现一个神奇的规律，每两组就加一个数，每一组数字就加一。如下：$f[1]=0,f[2]=1,f[3]=2,f[4]=2,f[5]=3,f[6]=3,f[7]=4,f[8]=4,f[9]=4,f[10]=5......$你发现了什么，这个有规律。如果你还是发现不了规律，那么就打个暴力dfs吧，让后再一次输出来，傻子都能发现规律。。。 让后接下来的就很简单了，模拟一次它运行时的操作，时间复杂度$O(t\sqrt{n})$ 快的飞起，详细证明这儿就不给出了(作者不会),似乎要用均值不等式，可我还是一个数学差的爆炸的初中生，证明是数学竞赛的事，不是我的事，呵呵。。。

code

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MAXN = 1e7 + 5; int t,n,pq = 1,cnt,step; int main() { freopen("list.in","r",stdin); freopen("list.out","w",stdout); scanf("%d",&t); while(t --) { scanf("%d",&n); while(n > 0) { n -= pq; cnt ++; step ++; if(cnt == 2) cnt = 0,pq ++; } printf("%d\n",step - 1); step = 0,pq = 1,cnt = 0; } return 0; }