在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第133题：叠叠高 的题目解析，具体如下：

题目描述

等级：容易
知识点：数论
查看题目：叠叠高

A同学买了n张卡片，他想用卡片来叠成一个塔，每层塔由数量不同的房间组成，且高层的房间数量必须少于低层的房间数量，房间可看做两张倾斜的卡片组成，两张卡片上面头部相接触。特殊的，每层的所有房间必须相邻，且高层的房间需要建在天花板上。

当n=13的时候只有以上两种方法去叠，但只能叠高度为2的塔。
相邻两个房间之间用一张卡片作为天花板相连。现在他想知道n张卡片全部使用的情况下他一共可以叠成多少种不同高度的塔。

输入一个整数n(1 <= n <= 10^9)，表示卡片数量；

输出一个数字，可以叠成的高度的种类数。
示例1
输入：
13
输出：
1

解题思路：数学题

题目中问的是可以组成多少种不同高度的塔。
首先计算每种高度的塔至少需要多少张卡片，然后判断多出来的卡片数与至少需要的卡片数之间的关系。
观察下图三层的塔。从上向下。
第一层一个房间，第二层两个房间，……，第i层i个房间。
一个房间需要2张卡片，两个房间需要5张卡牌（每个房间2张+天花板1张），……，i个房间需要2i+i-1 = 3i-1张。
这样每一层的卡片数都可以计算出来了，前k层的卡片数求和即可。记前k层最少需要f(k)张卡片

接下来观察多余卡片与房间的关系。下图中圈出来的房间位置从1层放到了2层。因此，对于多出来的卡片，我们可以都放到第一层处理（因为题目只问有多少种不同高度，而不是多少种不同的搭建方法）。
每多出来一间房，需要3张卡片（包括天花板）。所以多余的卡片为3的倍数，则这个高度的塔可以搭建。

计算过程
1、从第一层开始，计算f(i)，直到f(i)大于K。
2、判断每个f(i)与k的差值是否为3的倍数，是，则总数加1。
时间空间复杂度都很小。f(i)不需要一个数组来保存，只需要算出当前层的直接判断是否为3的倍数即可。

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：叠叠高