这道题目乍一看以为是很复杂的搜索，搜索各种情况，就没有细想。其实只要找规律加枚举就好了，夫神比赛时间做出来，膜拜夫神。

http://codeforces.com/contest/471/problem/C

找到规律就好办了，每一层至少一个2，表示最左侧，然后右侧没加一个要加3，没保持上层比下层小，所以至少是0+1+…h-1个room, 每个room用3，
剩下的只要堆在最底层就可以，满足3的倍数，于是算法成型

LL Room(LL n)
{
    LL ans=0;
    for(LL i=0;;i++)
    {
        LL num=i*(i+1)/2;
        LL remain=n-(i+1)*2-num*3;
        if(remain<0) break;
        if(remain%3==0) ans++;
    }
    return ans;
}

时间复杂度是n=(i+1)/2+3/2*i*(i+1) 中i的结果

i=(sqrt(4+24n)-4)/6=O(sqrt(n))

时间复杂度是O(sqrt(n))

Posted by richard爱闹 - 3月 7 2015
如需转载，请注明： 本文来自 Richard