美團筆試題練習

1.排序+周遊數組解決問題

讀懂題意，不要把此題想的過于複雜，由于淘汰的人數的可能取值，和臨界分數 m 一一對應，是以直接周遊排序後的分數數組，并在周遊過程中判斷淘汰數量和晉級數量的條件是否滿足。最先周遊到滿足條件的得分就是所求輸出。

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

int main() {
	int n, x, y, temp, b;
	cin >> n >> x >> y;
	vector<int> a;
	while (cin >> temp) {
		a.push_back(temp);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
		b = n - (i + 1);
		if ((i + 1) >= x && (i + 1) <= y && b >= x && b <= y) {
			cout << a[i];
			return 0;
		}
	}
	cout << -1 << endl;

}
           

2、排序+周遊數組解決問題

先對輸入的序列進行升序排列。我們需要明白，無論是什麼排列的正則序列，改動最少的方案一定是對輸入序列和正則序列中相同排名的元素進行修改，即輸入序列中排名第 i 的元素應該修改為正則序列中的 i。除此之外，其他的任何方案都至少存在一個數，使得它并不是修改為離它最近的正則序列中的數，這樣就會使得修改次數增多。

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

int main() {
	int n ,res = 0,temp = 0;
	cin >> n;
	vector<int> a;
	while (cin >> temp) {
		a.push_back(temp);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
        res += abs(a[i] - i - 1);
	}
	cout << res << endl;

}
           

3、排隊問題——采用優先隊列

拿到此題一看，屬于排隊問題，假設座位有序号，并且需要序号小的座位先被座，那麼，則采用算法複雜的較小的優先隊列，并且讓它有自動排序功能。

不用管坐了兩個人的桌子，坐了0個人的桌子坐了一個人之後出隊，入隊到坐了一個人的桌子的隊列裡邊；坐了1個人的桌子再坐了一個人之後出隊就不用管了

注意：輸出換行符用’\n’ 不逾時，用endl 則逾時。

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

int main() {
	int T;
	cin >> T;
	while (T--) {
		int N, M;
		string table, people;
		cin >> N;
		cin >> table;
		cin >> M;
		cin >> people;
		priority_queue<int, vector<int>, greater<int>> queue0, queue1;
		for (int i = 0; i < N; i++) {
			int temp = table[i] - '0';
			if (temp == 0)
				queue0.push(i + 1);
			else if (temp == 1)
				queue1.push(i + 1);
		}
		for (auto & x : people) {
			if (x == 'F') {
				if (!queue0.empty()) {
					int res = queue0.top();
					queue0.pop();
					queue1.push(res);
					cout << res << '\n';
				}
				else {
					int res = queue1.top();
					queue1.pop();
					cout << res << '\n';
				}
			}
			else {
				if (!queue1.empty()) {
					int res = queue1.top();
					queue1.pop();
					cout << res << '\n';
				}
				else {
					int res = queue0.top();
					queue0.pop();
					queue1.push(res);
					cout << res << '\n';
				}
			}
		}
	}
}