Codeforces Round #382 (Div. 2) C. Tennis Championship 递推、斐波拉契数列

Source

Codeforces Round #382 (Div. 2)

My Solution

题意：每个人输了比赛就会被淘汰，每两个人可以打比赛的要求是a赢过x场比赛b赢过y场比赛则当abs(x - y) <= 1 时他们可以进行比赛，总共n个选手，问最终的赢家可能赢过的场次的最大值。

递推、斐波拉契数列

递推是很好写的，cost[i] 表示赢i场比赛需要花费多少人，

则 cost[0] = 1,cost[1] = 2, cost[3] = cost[1] + cost[0],  cost[ans] = cost[ans-1] + cost[ans-2]一次类推直到n不够用，ans即为答案。

原来是斐波拉契数列，Y ^_^ Y

复杂度 O(85)

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

LL cost[maxn];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 5;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, ans = 0;
    cin >> n;
    cost[ans] = 1;
    ans++; n -= 2;
    cost[ans] = 2;
    while(true){
        if(n >= cost[ans - 1]){
            n -= cost[ans - 1];
            ans++;
            cost[ans] = cost[ans - 1] + cost[ans - 2];
        }
        else break;
    }

    cout << ans << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx