B - Pigeonhole Tower

一时失言乱红尘 2022-06-17 12:15 95阅读 0赞

Pigeon SSNA want to build a tower with some wood walls. Let's describe the tower they want to make:

1.  A Tower can consist of different number of level.
2.  If a tower contain **L **levels then 1st level must contain **L ** holes , 2nd level **L-1 , **3rd level **L-2** ….. **L** level contain 1 hole .
3.  Each room contain 3 wood walls.

See the picture below:

<table style="color:rgb(0,0,0); font-family:Merriweather,serif; font-size:18px"> 
 <tbody> 
  <tr> 
   <td><img title="3 level" src="https://odzkskevi.qnssl.com/25451059e47cf12f366663249ad81188?v=1492524646" alt="3 level" width="135" height="100"></td> 
   <td><img title="4level" src="https://odzkskevi.qnssl.com/700b99c8e3b5bedc81e6d93685271f05?v=1492524646" alt="4level" width="130" height="110"></td> 
  </tr> 
  <tr> 
   <td align="center">3 Level Tower</td> 
   <td align="center">4 Level tower</td> 
  </tr> 
 </tbody> 
</table>

Now pigeon SSNA has **n** wood walls. What is maximum number of level he can made.

### Input ###

Input starts with an integer **T** (≤ 100000), denoting the number of test cases.

Each case starts with a line containing an integer **n** (1 ≤ **n** ≤ 1012)

### Output ###

For each case of input you have to print the case number and expected answer.

<table style="color:rgb(0,0,0); font-family:Merriweather,serif; font-size:18px"> 
 <tbody> 
  <tr> 
   <td> <p><strong>Sample Input</strong></p> </td> 
   <td> <p><strong>Output for Sample Input</strong></p> </td> 
  </tr> 
  <tr> 
   <td> <pre style="white-space:pre-wrap; word-wrap:break-word">2
15
24</pre> </td> 
   <td> <pre style="white-space:pre-wrap; word-wrap:break-word">Case 1: 3
Case 2: 4</pre> </td> 
  </tr> 
 </tbody> 
</table>

题意：给出一个数，代表边的条数，问能够搭建几层（要能完整的搭建，比如输入为4，那输出只能是1，不能是2），1,2层输出0.    二分查找

#include<iostream>
    #include<queue>
    #include<cstdio>
    using namespace std;
    #define LL long long
    LL f[1000001];
    int main()
    {
        int t,l,r;
        LL n;
        f[0]=0;
        for(int i=1; i<=1000000; i++)
            f[i]=f[i-1]+1+2*i;
        scanf("%d",&t);
        int cas=1;
        while(t--)
        {
            l=1,r=1000000;
            scanf("%lld",&n);
            if(n<3)
                printf("Case %d: 0\n",cas++);
            else
            {
                int mid=(l+r)/2;
                while(l<r&&f[mid]!=n)
                {
                    if(f[mid]>n)
                        r=mid-1;
                    else if(f[mid]<n)
                        l=mid+1;
                    mid=(l+r)/2;
                }
                printf("Case %d: %d\n",cas++,f[mid]<=n?mid:mid-1);
            }
        }
        return 0;
    }