Map映射模擬佇列（南昌理工學院ACM集訓隊）
Map是由key到value組成的映射，每一個key對應一個唯一的value，因此在資料量非常大的時候能用Map映射快速檢索到相應的元素，
①Map包含在頭檔案#include<map>中
②定義map<key,value>name;
key為被映射的資料型別，value表示key映射到的資料型別，map的key和value可以是int、long long、struct 等等任意的資料型別，name為映射的名字
因為Map可以直接快速搜索到key對應的value，所以當資料非常大的時候我們可以用Map模擬佇列用BFS的方式解決問題
例題
洛谷U129453 「EZEC-4.5」占座位
題目描述
圖書館內有 nnn 個座位圍成一個圈，編號依次為 1～n，若干人依次進入圖書館占座位，
但是他們不想與他人靠得太近，因此他們占座位有 3個原則：
①第一個人選擇 1號座位，
②設 d(x) 為 x 號座位與其旁邊最近的人之間的空座位數（即不包括這兩個座位）， 從第二個人開始，每個人都會坐在使 d(x) 最大的座位 x 上，若有多個座位滿足條件，坐在編號最小的座位上，
③若沒有任何空座位 x 滿足 d(x)≥k ，則無法再坐人，
例 若n = 7，k = 1
因為這是一個圓桌，每一個人去坐都會盡量使周圍兩邊的空位最多，所以相當于每個人都會把剩余空位盡量分成兩半，因此可以用二叉樹來模擬，
7
|
6
/ \
2 3
/ \
1 1
例 若 n = 17 ， k = 2
17
|
16
/ \
7 8
/ \ / \
3 3 3 4
每個節點的權值代表剩余的空位，每個節點向下延伸的時候都-1，代表去掉自己的位置剩余的空位，一直到權值無法大于等于2為止
剩下的部分就是檢索總共有多少個有子節點的節點，然后將結果輸出就行
定義一個map
map<long long,long long>jd;
第一個long long代表節點的權值
第二個long long代表相應權值的數量
例如有三個權值為5的結點，則jd[5]=3;
接下來按照bfs的思路，將第一個map映射進入回圈，若可以分出子節點則將子節點輸入佇列，如果佇列里已經有與子節點權值相同的映射則將其加上父節點的權值，然后將原節點洗掉，最后判斷map是否為空，若為空則結束回圈
rbegin() 指向容器的最后一個元素
rbegin()->first 為最后一個元素的key
if (!jd.empty()) {
n = jd.rbegin()->first;//回傳map中最后一個元素的key（相當于佇列中的front()）
}
同理 rbegin()->second 為最后一個元素的value
下面是代碼部分
#include<iostream>
#include<map>
using namespace std;
#define ll long long
ll k, ans = 0;
map<ll, ll>jd;//定義一個map映射，所代表的是結點的權值和權值為這個數的數量
void bfs(ll n) {
while (!jd.empty()) {//當map為空時退出回圈
if (n % 2 == 0) {
if (n / 2 > 2 * k) {
if (jd[n / 2]) jd[n / 2] += jd[n];
else jd[n / 2] = jd[n];//map中沒有key代表的映射，則創建一個新的映射
ans += jd[n];
}
if (n / 2 - 1 > 2 * k) {
if (jd[n / 2 - 1]) jd[n / 2 - 1] += jd[n];
else jd[n / 2 - 1] = jd[n];
ans += jd[n];
}
}
else if (n % 2 != 0 && (n - 1) / 2 > 2 * k) {
if (jd[(n - 1) / 2]) jd[(n - 1) / 2] += jd[n] * 2;
else jd[(n - 1) / 2] = jd[n] * 2;
ans += jd[n] * 2;
}
jd.erase(n);//清除n代表的映射，類似佇列中的pop
if (!jd.empty()) {
n = jd.rbegin()->first;
}
}
}
int main()
{
ll n;
cin >> n >> k;
jd[n-1] = 1;//一開始1號位坐了第一個人，剩余空位為n-1
bfs(n-1);
cout << ans + 2 << endl;//最后結果加上一開始減去的兩個人就是最后的答案
}
蒟蒻代碼碼風比較亂看懂就好QAQ
下面是官方題解與思路（膜拜大佬）
U129453 「EZEC-4.5」占座位-君のNOIP， 的博客
當然題目可能還有其他的做法，畢竟大犇千千萬，蒟蒻我一人 ~o( =∩ω∩= )m
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/249795.html
標籤：其他