Problem #3342 - ECNU Online Judge

Fifnmar

4 年，3 月前

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

二分法中，在 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;
    }
}

回复 1 0

shwei

3 年，11 月前

#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;
}

回复 0 0

柴柴柴拆柴柴

4 年，3 月前

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

#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;
        }
    }
}

回复 0 0

Fifnmar

4 年，3 月前

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

回复 1 0

Chains.Z

4 年，1 月前

刷水题是真的会上瘾的 :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;
    }
}

回复 0 0

3342. 经典的猜数游戏

服务

开源

关于我们