最後更新日期 2024 / 01 / 01

題解 CSES Restaurant Customers

https://cses.fi/problemset/task/1619/

題意

給你 n 位客人的進入和離開餐廳的時間
輸出最多同時有幾位客人同時在餐廳

  • n2×105

想法

把每個人加入時間和離開的時間分別看成兩個時間點
並把所有時間點加入陣列後一起排序
然後用一個變數來維護目前餐廳人數
每次遇到加入就增加
反之遇到離開就減少
維護中遇到的最大值就是答案了
時間複雜度:O(n)

實作

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
signed main() {
	int n;
	cin >> n;
	vector<pii> v;
	for (int i = 0; i < n; i++) {
		int s, t;
		cin >> s >> t;
		v.push_back({s, true});
		v.push_back({t, false});
	}
	sort(v.begin(), v.end());
	int cur = 0;
	int ans = 0;
	for (auto e : v) {
		if (e.ss == true) cur++;
		else cur--;
		ans = max(cur, ans);
	}
	cout << ans << endl;
}

推薦文章

題解 CSES Repetitions

你有一個由 A、C、G、T 組成的字串 目標是算出同樣的字母最多連續重複幾次把整個字串從左邊往右掃 用一個 curLen 變數維護目前的長度 遇到一個字母時 curLen 加 1 如果跟上個字母不同就把 curLen 歸零 每次掃過一個字母再用 maxLen 維護出現過最大的 curLencppusing namespace std;signed main { char chr, tmp = 'X'; int maxLen = 1, curLen = 1; while cin chr { if tmp = 'X' tmp == chr { curLen++; } else { curLen = 1; } maxLen = maxmaxLen, curLen; tmp = chr; } cout maxLen endl;}

CSES

題解 CSES Missing Number

給予一堆數字 1 sim n 但中間缺少了一個 你的任務是找出那個缺少的數字已知數字 1 sim n 的總和為 sum^n{k=1}k 可以透過梯形公式 frac{n1 + n}{2} 快速求出來 所以我們只要用期望的 1 sim n 總和減掉輸入的所有數字就可以算出答案了cppusing namespace std; main { iosbase::syncwithstdiofalse;cin.tie0; int n, sum = 0; cin n; for int i = 0; i n-1; i++ { int tmp; cin tmp; sum += tmp; } cout 1 + n n 2 - sum endl;}

CSES

題解 CSES Permutations

給予一個數字 n 你要使用數字 1 sim n 構造一個陣列 使得不存在任意兩個相鄰數字的差為 1把 n 個數字分成 1 sim lfloor frac{n}{2} rfloor 和 lfloor frac{n}{2}+1 rfloor sim n 兩堆 並穿插構造 ans 陣列就可以保證任兩數的差大約為 lfloorfrac{n}{2}rfloor 最後跑過整個陣列驗證是否合法即可cppusing namespace std;signed main { iosbase::syncwithstdiofalse;cin.tie0; int n; cin n; vectorint arrn; dequeint ans; int mid = n2; for int i = 1; i = n2; i ++ { int leftVal = i; int rightVal = mid + i; ans.pushbackrightVal; ans.pushbackleftVal; } if n 1 == 1 { ans.pushfrontmid + n2 +1; } for int i = 0; i n-1; i++ { if absansi+1 - ansi == 1 { cout "NO SOLUTION" endl; return 0 ; } } for int i = 0; i n; i ++ { cout ansi " "; } cout endl;}

CSES