【CSES】1091. Concert Tickets

題目連結

時間複雜度

• $O(NlogN)$

解題想法

這題我剛開始解的時候原本打算用陣列去存，但是在寫完之後才發現有 TLE 的問題，所以我後面才改成用現在這個 MultiSet 來處理，然就過ㄌ

但是其實這個解法的複雜度沒有到很好，因為 Multiset 的 erase 函式其實時間複雜度最差是可以到

$O(N)$ 的，我也很好奇他為甚麼會過w

完整程式

/* Question : CSES 1091. Concert Tickets */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e7 + 50;
const int Mod = 1e9 + 7;
int n, m, h, t;
multiset<int> tickets;

signed main() {
	opt;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> h;
		tickets.insert(h);
	}
	for (int i = 0; i < m; ++i) {
		cin >> t;
		auto it = tickets.upper_bound(t);
		if (it == tickets.begin()) {
			cout << -1 << "\n";
		} else {
			cout << *(--it) << "\n";
			tickets.erase(it);
		}
	}
}