C. Computer Game——（普通二分查找）（CF-1400）

矫情吗；* 2024-04-18 13:01 39阅读 0赞

###### 题目： ######

[题目连接][Link 1]  
该题的题意是：  
Vova在打电脑游戏，他很想打完这局游戏  
①起初，他的电脑有**k**的电量， 这局游戏有**n**回合。  
②每次有三种选择：

*  当前电量大于a时， 他可以选择只打游戏， 然后打完这局电量减少a
 *  当前电量大于b(b <a)时， 他可以选择边打游戏边充电， 然后打完这局电量减少b
 *  如果当前电量不大于a和b， 他什么也不能做， 并且失去游戏

③求，如果Vova能打完这局游戏的话， 输出他 选择只打游戏的最大次数，  
如果不能打完这局输出-1.

###### 思路： ######

该题就是二分查找（不好意思， 我看到标签了罒ω罒），  
为什么是二分呢， 因为 如果答案存在， 他的答案应该是连续， 这是二分的必要条件（自己的总结， 如果答案不满足连续性 不要二分）。  
其他的看代码吧。

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const ll up = 1e9+1;
    ll check(ll k, ll n, ll a, ll b, ll tim)// 判断 选择 tim次a 是否满足题目要求
    { 
    
        if(tim*a < k)// 首先满足 要求1 
        { 
            k-=tim*a;
            ll tim_b = k%b==0?k/b-1:k/b;// 在满足 要求2的前提下 求出 b的次数
            if(tim_b+tim>= n)return true;// 如果那打完游戏返回true
            else return false;// 否则 false
        }
        else// 不满足 返回false
        { 
            return false;
        }
    }
    
    ll binSearch(ll k, ll n, ll a, ll b)// 二分查找选择a的次数, 要使a尽可能的大，
    { 
        ll l = 0, r = up;
        ll ans = -1;
        while(l<= r)
        { 
            ll mid = (l+r)>>1;
            if(check(k, n, a, b, mid))
            { 
                ans = mid;
                l = mid+1;
            }
            else
            { 
                r = mid-1;
            }
        }
    
        return min(ans, n);//答案不能大于 n回合
    }
    
    int main()
    { 
        ios_base::sync_with_stdio(false);
        ll q;
        cin>>q;
    
        while(q--)
        { 
            ll k, n, a, b;
            cin>>k>>n>>a>>b;
    
            cout<<binSearch(k, n, a, b)<<endl;
    
    
        }
    
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/1183/C