Ý tưởng bài toán

Chào mọi người ạ, em đang bí ở bài toán này ạ. (đề bài trong ảnh)

-Cách đầu tiên em nghĩ đến là mảng đánh dấu nhưng đề cho số phần từ là 10^9 nên không sử dụng được.

Ý tưởng của em:
Với d là ô nhớ có thứ tự nhỏ nhất chưa được sử dụng, d=0;

-Mỗi số nhập vào em sẽ cập nhật vào mảng, sắp xếp lại các giá trị.
-Khi gặp dấu ‘?’ em sẽ tìm d trong mảng, nếu không có sẽ return d; ngược lại d++

Nhưng nó vẫn chạy rất lâu khi gặp test lớn (dù sắp xếp = qsort(), và tìm kiếm nhị phân), mọi người cho em xin ý tưởng với ạ.

1 Like

Suy nghĩ khác đi 1 chút, khi bạn sử dụng 1 ô nhớ i, thì nó sẽ chia vùng nhớ thành 2 phần phía trước i và phía sau i.

Theo ví dụ trong đề:

  • i=1, vùng nhớ trống: 0~0 và vùng nhớ 2~10^9
  • ? => lấy ô 0 từ vùng nhớ 0~0 => vùng nhớ trống: 2~10^9
  • 2 => vùng nhớ trống: 3~10^9
  • ? => lấy ô 3 …
3 Likes

cảm mơn bạn, nhưng cho mình hỏi với trường hợp nhiều khoảng nhớ thì lưu trữ giá trị bằng cách nào
vd:
input: 3 ? 5 6 ?
i = 3, vùng nhớ trống là 0->2 và 4 -> 10^9
? -> 0, vùng nhớ trống là 1->2 và 4 -> 10^9
i = 5, vùng nhớ trống là 1->4 (trừ 3) và 6 -> 10^9
lúc này mình có 3 khoảng là 1 --> 2 , 4 , 6 -> 10^9
trong nhiều trường hợp có nhiều khoảng như vậy thì làm sao để tính ạ

Đây là dạng online của bài Tìm số tự nhiên nhỏ nhất ko có trong dãy. Bạn đang sắp xếp sau mỗi truy vấn loại 1, nhưng mỗi truy vấn loại 1 sẽ có độ phức tạp O(QlogQ). Bạn cần dùng Set để giảm còn O(logQ).

3 Likes

Suy luận tự nhiên thì linked list hoặc skip list sẽ phù hợp cho dạng này, với mỗi node sẽ chứa 1 cặp [start, end] (inclusive) của khoảng trống:

  • init: list: (0, 10^9)
  • i=3 => list: (0,2) -> (4, 10^9)
  • ? => list: (1, 2) -> (4, 10^9)
  • i=5 => list: (1, 2) -> (4, 4) -> (6, 10^9)
2 Likes

có thể xài set<pair<int, int>> với custom comparator cho pair<int, int>, mỗi pair đại diện cho 1 đoạn số [a, b]. pair 1 < pair 2 khi b1 + 1 < a2. Ví dụ khi insert 6,9,2,13,8,14,10,7,5 thì thực hiện như sau:

  • ban đầu set rỗng
  • insert 6: tìm [6,6] trong set, ko thấy, insert [6,6]
    -> set chứa [6,6]
  • insert 9: tìm [9,9] trong set, ko thấy, insert [9,9]
    -> set chứa [6,6], [9,9]
  • insert 2: tìm [2,2] trong set, ko thấy, insert [2,2]
    -> set chứa [2,2], [6,6], [9,9]
  • insert 13: tìm [13,13] trong set, ko thấy, insert [13,13]
    -> set chứa [2,2], [6,6], [9,9], [13,13]
  • insert 8: tìm [8,8] trong set, thấy [9,9], xóa [9,9] khỏi set, tìm tiếp [8,8] trong set, ko thấy, vậy merge [8,8] và [9,9] được [8,9], insert [8,9] lại vào set
    -> set chứa [2,2], [6,6], [8,9], [13,13]
  • insert 14: tìm [14,14] trong set, thấy [13,13], xóa [13,13] khỏi set, tìm tiếp [14,14] trong set, ko thấy, vậy merge [14,14] và [13,13] được [13,14], insert [13,14] lại vào set
    -> set chứa [2,2], [6,6], [8,9], [13,14]
  • insert 10: tìm [10,10] trong set, thấy [8,9], xóa [8,9] khỏi set, tìm tiếp [10,10] trong set, ko thấy, vậy merge [10,10] và [8,9] được [8,10], insert [8,10] lại vào set
    -> set chứa [2,2], [6,6], [8,10], [13,14]
  • insert 7: tìm [7,7] trong set, thấy [6,6], xóa [6,6] khỏi set, tìm tiếp [7,7] trong set, thấy [8,10], xóa [8,10] ra khỏi set, merge [7,7], [6,6] và [8,10] được [6,10], insert [6,10] lại vào set
    -> set chứa [2,2], [6,10], [13,14]
  • insert 5: tìm [5,5] trong set, thấy [6,10], xóa [6,10] khỏi set, tìm tiếp [5,5] trong set, ko thấy, vậy merge [5,5] và [6,10] được [5,10], insert [5,10] lại vào set
    -> set chứa [2,2], [5,10], [13,14]

còn tìm số bé nhất thì xài 1 biến int m = 0, mỗi khi hỏi thì tìm [m,m] trong set (chỉ cần xét với set.begin() là đủ), nếu ko thấy thì insert m. Nếu thấy m thuộc [a,b] thì gán m = b + 1 rồi insert m :V

bước insert tìm và xóa tối đa 2 lần, cộng thêm 1 lần insert, vậy là 5 operations, 5 * O(logn) vẫn là O(logn)
bước ? tìm m bé nhất là O(1) vì chỉ so sánh với set.begin() :V sau đó insert thì O(logn).
tổng cộng n lần là O(nlogn). 10^6 thì hơi vật vã :innocent:

code mẫu :face_with_monocle:

#include <set>

struct MySet {
    struct ClosedInterval {
        int a;
        int b;
        ClosedInterval(int a, int b) : a{a}, b{b} {}
        bool operator<(const ClosedInterval& rhs) const {
            return b + 1 < rhs.a; //
        }
        void mergeWith(const ClosedInterval& other) {
            if (b + 1 == other.a) b = other.b;
            else /*if (other.b + 1 == a)*/ a = other.a; 
        }
    };
    std::set<ClosedInterval> s;
    int m = 0;
    void insert(int k) {
        ClosedInterval kk{k, k};
        if (auto it = s.find(kk); it != end(s)) {
            kk.mergeWith(*it);
            s.erase(it);
            if ((it = s.find(kk)) != end(s)) {
                kk.mergeWith(*it);
                s.erase(it);
            }
        }
        s.insert(kk);
    }
    int findMinNotInSet() {
        if (!s.empty()) {
            auto& [a, b] = *begin(s);
            if (a <= m && m <= b) m = b + 1;
        }
        return m;
    }
};

chôm ý tưởng từ https://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf :imp:

5 Likes
#include <bits/stdc++.h>
const int mx  = 1e6;
using namespace std;
bool f[mx+1];
int q, cpoint = 0;
int main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cin >> q;
    while(q--)
    {
        string s;
        cin >> s;
        if (s[0] == '?')
        {
            cout << cpoint << '\n';
            f[cpoint++] = 1;
//            cout << cpoint << endl;
            while (f[cpoint] == 1) cpoint++;
        }
        else
            if (s.size() <= 6)
        {
            int n = 0;
            for(char i:s)
                n = n * 10 + (i-'0');
//                cout << "n = " << n << endl;
            f[n] = 1;
            while (f[cpoint] == 1) { cpoint++; }
        }
    }
}

bài này em bị rối khi nhìn test quá lớn nhưng khi phân tích kỹ thì có thể dùng mảng đánh dấu khi i<1e6

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?