BOJ 10816. デジタルカード2

質問する

コード#コード#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, aNum, bNum;
    cin >> n;
    vector<int> a;
    vector<int> b;
    for (int i = 0; i < n; i++)
    {
        cin >> aNum;
        a.push_back(aNum);
    }
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> bNum;
        b.push_back(bNum);
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < b.size(); i++)
    {
        int cnt = 0;
        int temp = b[i];

        int left = 0;
        int right = a.size() - 1;

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

            if (a[mid] == temp)
            {

                cnt++;
                if (a[mid + 1] != temp)
                {
                    right = mid - 1;
                    continue;
                }
                else
                {
                    left = mid + 1;
                    continue;
                }
            }
            else if (a[mid] < temp)
            {
                left = mid + 1;
            }
            else if (a[mid] > temp)
            {
                right = mid - 1;
            }
        }
        b[i] = cnt;
    }

    for (int i = 0; i < b.size(); i++)
    {
        cout << b[i] << ' ';
    }

    return 0;
}

の数字が非常に大きいので、BFのようにすればタイムアウトになるので、二分探索でアプローチすることにしました.

分間の探索により,所望の値を見つけることに成功した.

ただし、1つ以上の値が目的の場合、右側にない場合は問題が発生します.
左から検索してみました.

、cnt++を1つ増加するごとに

まだ問題があります!!両方に同じ数字があれば、どう処理すれば複雑になりますか.

このとき、数字が出始めたインデックス~最後に出たインデックスの数を加算すると、カードの数が出てきます.

の簡単な方法はlower_bound、upper_bound

である.

コード2

ヘッダファイル:<algorithm>STLライブラリlower_bound、upper_boundを使用

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, aNum, bNum, target;
    cin >> n;
    vector<int> a;

    vector<int>::iterator lower;
    vector<int>::iterator upper;
    for (int i = 0; i < n; i++)
    {
        cin >> aNum;
        a.push_back(aNum);
    }
    sort(a.begin(), a.end());
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> target;
        upper = upper_bound(a.begin(), a.end(), target);
        lower = lower_bound(a.begin(), a.end(), target);

        cout << upper - lower << ' ';
    }

    cout << '\n';
    return 0;
}

lower_bound:この数字が最初に現れた位置upper_bound:数字の終了位置

コード3

関数で実装されたコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lower_binary(vector<int> v, int target, int size)
{
    int mid;
    int left = 0, right = size - 1;
    while (right > left)
    {
        mid = (left + right) / 2;
        if (v[mid] >= target)
            right = mid;
        else
            left = mid + 1;
    }

    return right;
}
int upper_binary(vector<int> v, int target, int size)
{
    int mid;
    int left = 0, right = size - 1;
    while (right > left)
    {
        mid = (left + right) / 2;
        if (v[mid] > target)
            right = mid;
        else
            left = mid + 1;
    }

    return right;
}
int main(int argc, char const *argv[])
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, aNum, bNum, lower, upper;
    cin >> n;
    vector<int> a;
    vector<int> b;
    for (int i = 0; i < n; i++)
    {
        cin >> aNum;
        a.push_back(aNum);
    }
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> bNum;
        b.push_back(bNum);
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < b.size(); i++)
    {
        lower = lower_binary(a, b[i], n);
        upper = upper_binary(a, b[i], n);
        if (upper == n - 1 && a[n - 1] == b[i])
            upper++;

        b[i] = upper - lower;
    }

    for (int i = 0; i < m; i++)
    {
        cout << b[i] << '\n';
    }

    return 0;
}