ZOJ 3768Continuous Login(找規律然後二分)

Continuous Login

---

Time Limit: 2 Seconds Memory Limit: 131072 KB Special Judge

---

Pierre is recently obsessed with an online game. To encourage users to log in, this game will give users a continuous login reward. The mechanism of continuous login reward is as follows: If you have not logged in on a certain day, the reward of that day is 0, otherwise the reward is the previous day's plus 1.

On the other hand, Pierre is very fond of the number N. He wants to get exactly N points reward with the least possible interruption of continuous login.

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

There is one integer N (1 <= N <= 123456789).

Output

For each test case, output the days of continuous login, separated by a space.

This problem is special judged so any correct answer will be accepted.

Sample Input

4
20
19
6
9

Sample Output

4 4
3 4 2
3
2 3

Hint

20 = (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4)

19 = (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2)

6 = (1 + 2 + 3)

9 = (1 + 2) + (1 + 2 + 3)

Some problem has a simple, fast and correct solution.

---

Author: ZHOU, Yuchen
Source: The 14th Zhejiang University Programming Contest




題目大意：意思讓你找最少的組數，使得找的所有的組等差數列和的全部和為所給數，具體題目意思看下題目的數列形式即可。
解題思路：
好吧，思路開始天馬行空的，先打了個表存放前n項和，發現打到13000。然後就開始yy了，想直接從大往小找，但發現不能保證組數最小。
然後想寫bfs，但是標記又標不了，發現還是不行，於是開始找規律。
我列舉了1~20可以拆分的，發現最多只有三組。
然後就開始敲代碼了，但是還是不是很確定。就讓豪爺在旁邊寫枚舉前100項的分組數，，

先看能不能分一組，如果可以就一組，
不行再試下兩組，第一組枚舉，第二組二分。
不行就試下三組，枚舉前兩組，第三組二分。
如果實在不行，就沒辦法了。
其實，我二分還debug了半天，，，，
算法復雜度O（n*n*log2(n)）
題目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5231
AC代碼：

#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;

int dp[20005];
int len;

int erfen(int x)
{
    int l=1,r=len;
    int mid;
    mid=(l+r)>>1;

    while(r>l)
    {
        if(dp[mid]==x) return mid;
        if(dp[mid]>1;
    }

    if(dp[l]>x) l--;
    return l;
}

int main()
{
    int i;
    dp[0]=0;
    dp[1]=1;
    for(i=1;i<=20000;i++)
    {
        dp[i]=dp[i-1]+i;
        if(dp[i]>=123456789)
            break;
    }

    len=i;

    int tes,n;
    cin>>tes;

    int a,b,c;
    while(tes--)
    {
        cin>>n;
        int p=erfen(n);
        if(dp[p]==n)
        {
            printf("%d\n",p);
            continue;
        }

        int flag=0;
        for(a=p;a>=1;a--)
        {
            b=erfen(n-dp[a]);
            if(dp[b]+dp[a]==n)
            {
                flag=1;
                break;
            }
        }

        if(flag)
        {
            printf("%d %d\n",a,b);
            continue;
        }

        flag=0;
        for(a=p;a>=1;a--)
        {
            int s=erfen(n-dp[a]);
            for(b=s;b>=1;b--)
            {
                c=erfen(n-dp[a]-dp[b]);
                if(dp[a]+dp[b]+dp[c]==n)
                {
                    flag=1;
                    break;
                }
            }
            if(flag) break;
        }

        if(flag)
        {
            printf("%d %d %d\n",a,b,c);
            continue;
        }
    }
}