BOJ 10816-デジタルカード2

10275 ワード
algorithm sorting binary_search boj テキストリンク
Problem
https://www.acmicpc.net/problem/10816
最初に持っているカードを受け取ります.
そして、何個の入力カードが出力されますか.
Solution
Binary Searchを用いて,下界と上界を用いて正解を求めることができる.

  • 下限:数以上の最初の数

  • 上界:大数の最初の数
    • 1334553의 lower bound : 3 (index = [1]) 3의 upper bound : 4インデックスを上下にすると、同じ数の数字が表示されます.3(index of upper b) - 1(index of lower b) = 2下線は同じ数がある場合に最初の位置を見つけなければならないので、数が見つかったら、下線を保存し、right mid-1が完了した後、ナビゲーションを続行します.
    上界は値が見つかったときより大きな値をとるため、上界ではmid+1、leftもmid+1の後にナビゲーションを継続する.
    Code
    #include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    cin >> m;

    while (m--) {
        int goal;
        cin >> goal;

        int left = 0;
        int right = n - 1;
        int lb, ub;
        lb = 0;

        //lower bound
        while (left <= right) {
            int mid = (left + right) / 2;

            if (a[mid] == goal) {
                lb = mid;
                right = mid - 1;
            }

            else if (a[mid] > goal) {
                right = mid - 1;
            }

            else {
                left = mid + 1;
            }
        }

        left = 0;
        right = n - 1;
        ub = 0;

        //upper bound
        while (left <= right) {
            int mid = (left + right) / 2;

            if (a[mid] == goal) {
                ub = mid+1;
                left = mid + 1;
            }

            else if (a[mid] > goal) {
                right = mid - 1;
            }

            else {
                left = mid + 1;
            }
        }

        //같은수의 개수 = upper bound - lower bound
        cout << ub - lb << ' ';
    }

    return 0;
}
    注:https://code.plus/course/43、分割征服
    Flask Flask_セッションモジュール
    Spring Boot StringRedisTemplateの一般的な操作