[BOJ/C+]1072番ゲーム

6197 ワード
boj cpp テキストリンク
この問題は二分探索で解決できる.
  • low=0,high=1000000000.
  • midを(低+高)/2に設定し、x、yにmidを加え、tempz値をzと比較します.
  • zがtempz以上である場合、lowはmid+1に変換され、そうでない場合、highはmid−1に変換される.
  • 最終lowを結果として出力します.

    • Code

    #include <iostream>
using namespace std;

long long x, y, z;
long long tempz;
int low, high;

void Input(){
    cin>>x>>y;
    z=(100*y)/x;
}

int Solution(){
    if(z>=99){
        return -1;
    }
    else{
        low=0; high=1000000000;
        while(low<=high){
            int mid=(low+high)/2;
            tempz=(100*(y+mid))/(x+mid);
            if(z>=tempz){
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
    }
    return low;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<Solution()<<endl;
    return 0;
}
    [Algorithm]宜珍を探る?パラメトリック検索?🤔
    TIL 20.12.22