hdu 5312 Sequence

柔情只为你懂 2022-08-02 19:59 16阅读 0赞

#  #

# Sequence #

**Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)  
Total Submission(s): 878    Accepted Submission(s): 267**

Problem Description

Today, Soda has learned a sequence whose  *n*\-th  (*n*≥1) item is  3*n*(*n*−1)\+1. Now he wants to know if an integer  *m* can be represented as the sum of some items of that sequence. If possible, what are the minimum items needed?  
  
For example,  22=19\+1\+1\+1=7\+7\+7\+1.

Input

There are multiple test cases. The first line of input contains an integer  *T*  (1≤*T*≤104), indicating the number of test cases. For each test case:  
  
There's a line containing an integer  *m*  (1≤*m*≤109).

Output

For each test case, output  −1 if  *m* cannot be represented as the sum of some items of that sequence, otherwise output the minimum items needed.

Sample Input

10
    1
    2
    3
    4
    5
    6
    7
    8
    22
    10

Sample Output

1
    2
    3
    4
    5
    6
    1
    2
    4
    4

官方题解：

这个题看上去是一个贪心, 但是这个贪心显然是错的.事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的k(k>2)k (k > 2)k(k>2), 使得(m−k)mod6=0(m - k) mod 6 = 0(m−k)mod6=0即可.

证明如下:3n(n−1)+1=6(n∗(n−1)/2)+13n(n-1)+1 = 6(n\*(n-1)/2)+13n(n−1)\+1=6(n∗(n−1)/2)\+1, 注意到n∗(n−1)/2n\*(n-1)/2n∗(n−1)/2是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要kkk个, 那么显然m=6(km=6(km=6(k个三角形数的和)+k)+k)\+k, 由于k≥3k \\ge 3k≥3, 只要m−km-km−k是6的倍数就一定是有解的.

事实上, 打个表应该也能发现规律.

尽然还用到三角形数。。看了之后枚举还是超时，，后来才懂原来是在枚举2的时候超时了，开始的做法是枚举每个数与n的差值，用二分找差值，如果存在就枚举成功，时间复杂度是nlogn,但是还是超时（T比较大）。后来想到原数列是有序的，所以从原数列中找两个数的和为n可以用线性的算法。设置两个指针 l 和r 一个指向最前面，一个指向最后面，l指针不断往后，r指针不断往前，由于是排序好的，两个指针都不需要回溯。所以比较快。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline ll in()
    {
        ll res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int a[20005];
    int main()
    {
        mem(a,0);
        for(int i=1;i<=20000;i++)
        {
            a[i]=3*i*(i-1)+1;
        }
        int T=in();
        while(T--)
        {
            int n=in();
            int pos=lower_bound(a+1,a+20000,n)-a;
            if(a[pos]==n)          //枚举1
            {
                puts("1");
                continue;
            }
            int l=1,r=pos-1;
            bool ok=0;
            while(l<=r)    //枚举2
            {
                while(a[l]+a[r]>n)r--;
                if(a[l]+a[r]==n)
                {
                    ok=1;
                    break;
                }
                ++l;
            }
            if(ok)
            {
                puts("2");
                continue;
            }
            for(int i=3;i<=8;i++)//枚举3-8
            {
                if((n-i)%6==0)
                {
                    printf("%d\n",i);
                    break;
                }
            }
    
        }
        return 0;
    }