首页 > 其他 > 详细

1368A - Codeforces Global Round 8 - C+=

时间:2020-11-08 22:31:14      阅读:25      评论:0      收藏:0      [点我收藏+]

题目地址:https://codeforces.com/problemset/problem/1368/A

技术分享图片

 

 

题意:

定义一个操作为:“ += ",如  a += b ,即 a = a + b,求最小的操作次数使 make the value of either a or b strictly greater than a given value n.

思路:

要求最小次数,那必然是使得每次 a += b 中 a 值达到最大,从而保证每一步都最大化程度逼近n 

显然,对于a,b可以 min(a,b) += max(a,b),从而使得单步长最大化,then 不断循环即可。

按照上方的思路,只需要将 “+=” 操作完后的最大值与n进行比较,如果max(a,b) > n,循环终止,结束。

AC代码:

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    // freopen("x.txt","r",stdin);
    int t;
    cin >> t;
    ll a,b,n;
    while(t--){
        cin >> a >> b >>n;
        int all = 0;
        if(a > b) // 保证 a < b,b是较大值
            swap(a,b);
        while(b <= n){
            a += b;
            if(a > b){
                swap(a,b);
            }
            all++;
        }
        cout << all << endl;
    }
    return 0;
}

 

1368A - Codeforces Global Round 8 - C+=

原文:https://www.cnblogs.com/expedition/p/13946072.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!