CF1345B Card Constructions 题解

· · 题解

我是传送门

题目大意

你在玩一种扑克搭建金字塔的游戏，其中高度为 1、2、3 的金字塔是这个样子：

现在你有 n 张扑克牌，你有一种搭建策略：每次你会用你手中牌搭建可以搭建高度最大的金字塔，重复这个过程，直至手中的牌无法搭建任何一个金字塔。

问：你最多可以搭建几个金字塔？

分析

这题可以打表找规律。可以发现：

那么这个递推公式是怎么来的呢？

可以发现，每一个三角形都会有一个顶点是空的。补上这个空的地方需要 i-1 张扑克。

然后下方，还有加上 i 个最小的三角形要 2\times i 张扑克。然后就可以得出这个递推公式了。

用这个代码来获取高度并存在数组 h 中。

    for(int i=2;i<=30000;++i) 
    {
    h[i]=h[i-1]+(i-1)+2*(i);
    }

那么，就先试试直接打暴力搜索。

然后从 2 开始枚举。然后发现不行。

就只能去试试二分了。这里可以直接用函数 upper_bound 搜索第一个要用的扑克大于 n 的高度，然后 n 减去这个高度的扑克数就好了。

下面是 AC 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t,n,s,k,h[30000];
    cin>>t;
    h[1]=2;
    for(int i=2;i<=30000;++i) 
    {
    h[i]=h[i-1]+(i-1)+2*(i);
    }
    while(t--)
    {
        cin>>n;
        s=0;
        int i=1;
        while(n>=2)
        {
            int pos1=upper_bound(h,h+30000,n)-h; 
        //  cout<<h[pos1-1]<<" ";
            n-=h[pos1-1];
            s++;
        }

        cout<<s<<endl;
    }
    return 0;
}