3342. 经典的猜数游戏

Deuchie

二分搜索的经典例题。我在这里踩了一个坑,幸好,让我发现了一个思维漏洞。

二分法中,在 range [bg, ed) 里搜索,每次 mid = bg + (ed - bg) / 2。我起先对这种貌似多此一举的求中位方法不以为意,猜想可能是为了支持指针操作(不能把两个指针相加)。今天才发现原来还有确保对负数也成立的功能(如果是 mid = (bg + ed) / 2 的形式,会出现死循环)。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int bg = -1'000'000'000;
    int ed = 1'000'000'001;
    while (true) {
        int mid = bg + (ed - bg) / 2;
        cout << mid << endl;
        string a;
        cin >> a;
        if (a == "big")
            ed = mid;
        else if (a == "small")
            bg = mid + 1;
        else
            break;
    }
}
柴柴柴拆柴柴

这是一道交互题,因此要注意及时清空缓冲区

#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<string>

using namespace std;

int main()
{
    long lmax=1000000001;
    long lmin=-1000000001;
    long res;
    string answer;

    for(int i=0;i<32;i++){
        long res=(lmax+lmin)/2L;
        cout<<res<<endl;
        cout.flush();
        cin>>answer;
        if(answer=="big"){
            lmax=res;
        }
        else if(answer=="small"){
            lmin=res;
        }
        else if(answer=="equal"){
            break;
        }
    }
}
Deuchie

C++ ostream 的 endl 本身就会刷新缓冲区,没有必要显式地调用 os.flush()

Chains.Z

刷水题是真的会上瘾的 :p

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int max = 1e9;
    int min = -1e9;
    int mid = 0;
    cout << mid << endl;
    string input;
    while (cin >> input && input != "equal")
    {
        if (input == "big")
            max = mid - 1;
        else
            min = mid + 1;
        mid = (max + min) / 2;
        cout << mid << endl;
    }
}
shwei
#include <iostream>

using namespace std;

int main() {
    int l = -1e9, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        cout << mid << endl; // 交互题。先猜,把mid输出到标准输出流

        string s;
        cin >> s; // 对于我的回答,你要从标准输入流中读入
        if (s == "equal") break;

        if (s == "big") r = mid;
        else l = mid + 1;

    }


    return 0;
}
你当前正在回复 博客/题目
存在问题!