Gym

https://vjudge.net/problem/Gym-100283F

题意：

1 2 1

1 2 3 2 1

1 2 3 4 3 2 1 ....

给出这样的序列，然后给出一个n，计算从1+1+2+1+1+2+3...加到大于等于n至少需要多少个数。

思路：

二分法。

每一行的总和为，所以第i行之前的数总和为，所以我们可以可以利用二分法，确定第i行(第i+1行的总和大于了n)。接下来我们继续在第i+1行进行二分。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 
10 typedef long long LL;
11 
12 LL n;
13 
14 int main()
15 {
16     freopen("army.in","r",stdin);
17     /*
18     for(LL i=10000;;i++)
19     {
20         LL num=(i*(i+1)*(2*i+1))/6;
21         if(num>=1e18)
22         {
23             cout<<i<<endl;
24             break;
25         }
26     }
27     */
28 
29     int T;
30     int kase=0;
31     scanf("%d",&T);
32     while(T--)
33     {
34         scanf("%lld",&n);
35         LL ans=0;
36         LL L =0, R =1500000;
37         while(L+1<R)
38         {
39             LL mid =(L+R)/2;
40             LL num =mid*(mid+1)*(2*mid+1)/6;
41             if(num >= n) R=mid;
42             else L=mid;
43         }
44 
45         n-=L*(L+1)*(2*L+1)/6;
46         ans+=L*L;
47         if(n<R*(R+1)/2)
48         {
49             L=-1;
50             while(L+1<R)
51             {
52                 LL mid=(L+R)/2;
53                 LL num=mid*(mid+1)/2;
54                 if(num>=n)  R=mid;
55                 else L=mid;
56             }
57             ans+=R;
58         }
59         else
60         {
61             ans +=2*R-1;
62             n =R*R-n;
63             L =0;
64             while(L+1<R)
65             {
66                 LL mid =(L+R)/2;
67                 if(mid*(mid+1)/2 > n) R =mid;
68                 else L =mid;
69             }
70             ans -=L;
71         }
72         printf("Case %d: %lld
",++kase,ans);
73     }
74     return 0;
75 }