Ҳудудҳо, unique ва ҷойгузинӣ - Муқаддима ба барномасозӣ: C++

Ҳафтаи 18: Махзани стандартӣ

Ҳудудҳо, unique ва ҷойгузинӣ

Ҷойи қиматро дар вектори танзимшуда бо lower_bound ва upper_bound ёбед, нусхаҳои такрориро бо unique хориҷ кунед ва ҳамаи тартибҳоро бо next_permutation гузаред.

Назария
Дарси 2 аз 5
Хониш: 13 дақиқа
Саволҳо: 7

x дар куҷо меистад?

binary_search танҳо «ҳа» ё «не» мегӯяд. Ду функсияи монанд ба он мегӯянд, ки қимат дар куҷост. Ҳарду фосилаи мураттаб мехоҳанд ва тақрибан log₂ n қадам мегузаранд.

lower_bound(b, e, x) ҷойи аввалин ҷузъест, ки >= x аст.
upper_bound(b, e, x) ҷойи аввалин ҷузъест, ки > x аст.

Агар чунин ҷузъ набошад, ҳарду e медиҳанд. Фарқ дар он аст, ки бо нусхаҳои x чӣ мекунанд. lower_bound ба аввалин x ишора мекунад. upper_bound ба баъди охирини онҳо ишора мекунад. Ҳудудҳоро ҳамчун хатчаҳо миёни катакҳо тасаввур кунед.

Хатчаҳоро худатон ҷунбонед:

Ҳудудҳо ба куҷо ишора мекунанд?

навбатӣ

Машқ: махзани стандартӣ

Масъалаҳое, ки пеш аз навиштани сикл афзори мувофиқи махзанро интихоб мекунанд: min_element, count, find, lower_bound.

Дарси навбатӣ

Дарси пешина Ба харитаи курс

8 3
12 5 20 8 5 17 3 9
5 10
1 4
18 30

4
1
1

1 x2
3 x2
5 x3
9 x1
4 different

#include <bits/stdc++.h>
using namespace std;

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

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &v : a) {
        cin >> v;
    }
    // ҳудудҳо: мураттаб лозим
    sort(a.begin(), a.end());
    while (q--) {
        int lo, hi;
        cin >> lo >> hi;
        auto from = lower_bound(
            a.begin(), a.end(), lo);
        auto to = upper_bound(
            a.begin(), a.end(), hi);
        cout << to - from << "\n";
    }
    return 0;
}

// a ин 2 4 4 7 10 аст ва x = 9
auto it = upper_bound(
    a.begin(), a.end(), x);
if (it == a.begin()) {
    cout << "none\n";
} else {
    // як катак ба чап
    it--;
    cout << *it << "\n";
}

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int &v : a) {
        cin >> v;
    }
    // қиматҳои баробар ҳамсоя мешаванд
    sort(a.begin(), a.end());
    // як силсила: аз i то j - 1
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && a[j] == a[i]) {
            j++;
        }
        cout << a[i] << " x" << j - i
             << "\n";
        i = j;
    }
    a.erase(unique(a.begin(), a.end()),
            a.end());
    cout << a.size() << " different\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

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

    string s;
    cin >> s;
    // аз тартиби хурдтарин оғоз мекунем
    sort(s.begin(), s.end());
    int k = 0;
    do {
        cout << s << "\n";
        k++;
    } while (next_permutation(
        s.begin(), s.end()));
    cout << k << " orders\n";
    return 0;
}