首页 > 代码库 > codeforces 735C Tennis Championship(贪心+递推)

codeforces 735C Tennis Championship(贪心+递推)

Tennis Championship

题目链接:http://codeforces.com/problemset/problem/735/C

    ——每天在线,欢迎留言谈论。

题目大意:

给你一个 n (2≤n≤10^18),代表一共有n位参加比赛的选手。

游戏规则:

①每次比赛,输的选手将离开赛场

②相互比赛的选手 他们的获胜的次数相差不能超过1(获胜4次的选手只能跟3或5次的选手比赛)

问题:最终赢得比赛的选手,胜场最多能为多少。

思路:

贪心:①选一名选手让他一直获胜且优先让他参加比赛

②当没有可比赛选手的时候(比如他胜为2时,其他选手胜场为0),就让另一个人的胜场达到比他少一场(恰好可以比赛),然后比赛输掉.

递推:

技术分享

意思:产生一名胜场为x的选手,需要有y名选手出局

规律例:想要获得一胜5次的选手 需要 一名4次的选手+一名3次的选手 然后比赛后前者获胜后者出局。

n[i]=n[i-1]+n[i-2]+1(1为获胜 i-1 次的选手出局)

那么 : 答案就是n-1>=y对应的那个x对大的那个喽

AC代码:

 1 #include <iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a[91]={0,1};
 5 int main()
 6 {
 7     for(int i=2;i<=90;i++)
 8     {a[i]=a[i-1]+a[i-2]+1;}
 9     ll n;
10     cin>>n;
11     n-=1;
12     for(int i=1;i<=90;i++)
13         if(n<a[i])
14         {
15             cout<<i-1<<endl;
16             return 0;
17         }
18     //通过计算a[90]已经为 7e18多了,为题目给定n 的3倍多!
19     cout<<"90"<<endl;
20     return 0;
21 }

2017-05-27 19:25:29

codeforces 735C Tennis Championship(贪心+递推)