Sequence

 

 Accepts: 25

 

 Submissions: 1442

 Time Limit: 2000/2000 MS (Java/Others)

 

 Memory Limit: 262144/262144 K (Java/Others)

问题描述

Soda习得了一个数列, 数列的第nn (n \ge 1)(n≥1)项是3n(n-1)+13n(n−1)+1. 现在他想知道对于一个给定的整数mm, 是否可以表示成若干项上述数列的和. 如果可以, 那么需要的最小项数是多少?例如, 22可以表示为7+7+7+17+7+7+1, 也可以表示为19+1+1+119+1+1+1.

输入描述

输入有多组数据. 第一行有一个整数TT (1 \le T \le 10^4)(1≤T≤104), 表示测试数据组数. 然后对于每组数据:一行包含1个整数 mm (1 \le m \le 10^9)(1≤m≤109).

输出描述

对于每组数据输出最小花费.

输入样例

10123456782210

输出样例

1234561244

题解：

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

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

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

做的时候就想这题贪心肯定是WA，但最后还是稀里糊涂地贪心了。推的时候还在想n∗(n−1)/2这个式子应该有什么性质，但真不知道这个是三角形数，并且任意一个自然数最多只需要3个三角形数

就能表示了，也是通过这个题涨了姿势吧。

有了这个解题思路之后，以为程序就变得很好写了，结果在找两个的时候，写了两层循环，愤怒的TLE啊。。。

找两个的时候这段代码，又一次被教做人了：

while(i<=j)		{			if(sum_2[i]+sum_2[j] == cal)				return 2;			else if(sum_2[i]+sum_2[j]

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int cal,i,j,temp1,temp2,sum;//18528int sum_2[20000];int solve(){ if(cal%6==1) { for(i=1;i<18528;i++) { if(sum_2[i]
          
           cal) break; else if(sum_2[i]==cal) return 1; } return 7; } else if(cal%6==2) { i=1;j=18527; while(i<=j) { if(sum_2[i]+sum_2[j] == cal) return 2; else if(sum_2[i]+sum_2[j]
          
         
        
       
      
     
    

发现这个世界真是辽阔，每一次都能学到之前自己并不知道的，更加优化的算法。每一次都被虐得很抱怨，但每一次也都有很多收获。

版权声明：本文为博主原创文章，未经博主允许不得转载。