提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Codeforces Round #382 (Div. 2) C. Tennis Championship

2023-04-18 12:34:37 时间

 

   题目大意：有n个人参加网球比赛，按照淘汰赛制两两对打；但有个前提：对打的两个人他们所参加的比赛场次相差不能超过1。问：这次比赛的冠军最多能参加几场比赛？

    题解思路：可能一开始都会想着直接循环让n不断除2，然后计算除至1时所用的次数（我一开始就是这样狂wa的...=_=）；但题意是想要让最后的一个人尽可能多的参加比赛场次，所以上述方法并不是最优的方法。  不过 即使是用上面不正确的方法计算也可以知道一点：如果给出一个固定的最终结果x，符合结果的人数会是一个区间，这个区间的人数 经过比赛后 其冠军所经历的最多比赛场次都会是x。  那么，从贪心的角度上思考：我们是不可以算出 对于一个x 即比赛冠军最多可以打x场次比赛的话 ，其所需要的最少人数？  设f(x)为冠军能打x场次时所需要的最少人数；那么，接下来问题就是：如何确定这个f(x)为最少人数。—— 假设冠军打的最后一场次是他第x场次；那么，能让所用人数最少的话则是需要冠军已经打了x-1个场次，而他的对手打了x-2个场次； 这样一来，就有了递推公式：f(x)=f(x-1)+f(x-2) 。 显而易见是个斐波那契数列；预处理出斐波那契数列后，对于输入的n，二分该数列就是答案了。

 1 /**
 2 * @author Wixson
 3 */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <algorithm>
 9 #include <queue>
10 #include <stack>
11 #include <vector>
12 #include <utility>
13 #include <map>
14 #include <set>
15 const int inf=0x3f3f3f3f;
16 const double PI=acos(-1.0);
17 const double EPS=1e-10;
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int,int> P;
21 
22 ll fb[500005];
23 ll n;
24 int main()
25 {
26     //freopen("input.txt","r",stdin);
27     int l=1,r;
28     fb[1]=2,fb[2]=3;
29     for(int i=3;;i++)
30     {
31         fb[i]=fb[i-1]+fb[i-2];
32         if(fb[i]>1e18)
33         {
34             r=i;
35             break;
36         }
37     }
38     //
39     cin>>n;
40     //
41     while(l<=r)
42     {
43         int mid=(l+r)/2;
44         if(fb[mid]>n) r=mid-1;
45         else l=mid+1;
46     }
47     //
48     cout<<r<<endl;
49     return 0;
50 }

 

相关文章