1.pair
pair用于存儲兩個不同類型的值(元素)作為一個單元。它通常用于將兩個值捆綁在一起,以便一起傳遞或返回。
#include <iostream>
#include <utility>
using namespace std;
int main() {pair<int, string> person = make_pair(25, "jack");//存儲一對值并初始化
//可簡寫為 pair<int, string> person(25, "jack");cout << person.first << " " << person.second;//25 jack
}
嵌套
#include <iostream>
#include <utility>
using namespace std;
int main() {pair<int, pair<int, int>> people=make_pair(3, make_pair(4, 5));cout << people.second.first;//4return 0;
}
排序規則
優先考慮first,若相等再比較second…
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int main() {pair<int, std::string> people[] = {make_pair(25, "Alice"),make_pair(30, "Bob"),};sort(people, people + 2);for (int i = 0; i < 2; i++) {cout << people[i].first<< people[i].second << endl;}return 0;
}
2.vector
提供了動態數組(可變大小數組)的實現,存儲的事一系列相同類型的元素
#include <iostream>
#include <vector>
using namespace std;
int main() {vector<int> a;//定義整型a容器a.push_back(1);a.push_back(2);a.push_back(3);cout << a[0]<<endl;//首元素:1a.pop_back();//刪除尾部元素cout << a.size();//元素個數:2
}
元素插入操作
#include <iostream>
#include <vector>
using namespace std;
int main() {vector<int> a = { 5,4,3 };a.insert(a.begin() + 1, 999);cout << a[1];//999
}
初始化與排序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {//初始化vector<int> a(5, 1);//對容器a初始化為{1,1,1,1,1}vector<int> b = { 5,4,3,2,1 };//排序sort(b.begin(), b.end());for (int i = 0; i < b.size(); i++) {cout << b[i];//12345}
}
去重排序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<int> a = { 5,4,3,2,1,5,5 };sort(a.begin(), a.end());//unique只能去掉相鄰重復元素,所以先sort//auto用于自動推導 unique 函數返回的迭代器類型auto b = unique(a.begin(), a.end());auto n = distance(a.begin(), b);for (int i = 0; i < n; i++) {cout << a[i];//12345}
}
另一種去重排序方式
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<int> a = { 5,4,3,2,1,5,5 };sort(a.begin(), a.end());//1 2 3 4 5 5 5auto b = unique(a.begin(), a.end());//b指向了多余元素的起始位置(排序完成后的第二個5的位置)a.erase(b, a.end());//擦除從b到末尾的元素,a的大小也同時修改了。即刪除了后面的兩個5for (int i = 0; i < a.size(); i++) {cout << a[i];//12345}
}
輸出可以使用以下方式
循環變量 i 依次取 a 容器中的每個元素的值
const 保證了元素不會被修改
auto 使編譯器自動推斷元素的類型
& 表示使用引用來避免不必要的復制
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {vector<int> a = { 5,4,3,2,1,5,5 };sort(a.begin(), a.end());auto b = unique(a.begin(), a.end());a.erase(b, a.end());for (const auto& i : a) {cout << i;//12345}
}
3.list
較少使用
以節點存儲,以指針鏈接的鏈表結構
#include <iostream>
#include <list>
using namespace std;
int main() {// 創建一個空的 list,存儲整數list<int> myList;// 在列表末尾插入元素myList.push_back(1);myList.push_back(2);myList.push_back(3);//列表元素為123// 在列表開頭插入元素myList.push_front(6);//列表元素為6123// 遍歷列表并打印元素for (const auto& i : myList) {cout << i << " ";}cout << endl;//輸出了:6 1 2 3// 刪除列表中的元素myList.pop_back();myList.pop_front();//列表元素為12
}
4.stack
#include <iostream>
#include <stack>
using namespace std;
int main() {stack<int> myStack;// 壓棧操作myStack.push(1);myStack.push(2);myStack.push(3);//棧內(從下到上):123// 訪問棧頂元素cout << myStack.top();//3// 彈棧操作myStack.pop();//3被彈出// 再次訪問棧頂元素cout << myStack.top();//2//棧內(從下到上):12// 獲取棧中元素的數量cout << "Stack size: " << myStack.size() << endl;//2// 檢查棧是否為空if (myStack.empty()) {cout << "Stack is empty." << endl;}else {cout << "Stack is not empty." << endl;}
}
5.queue
(1)普通隊列
#include <iostream>
#include <queue>
using namespace std;
int main() {queue<int> myQueue;// 入隊操作myQueue.push(1);myQueue.push(2);myQueue.push(3);//隊列(從頭到尾):123// 訪問隊頭元素cout << myQueue.front();//1// 出隊操作myQueue.pop();//1出// 再次訪問隊頭元素cout <<myQueue.front();//2//隊列(從頭到尾):23// 獲取隊列中元素的數量cout << myQueue.size();//2// 檢查隊列是否為空if (myQueue.empty()) {cout << "Queue is empty." << endl;}else {cout << "Queue is not empty." << endl;}
}
(2)優先隊列/堆
隊列中的元素是按照一定優先級進行排序的,默認情況下是從小到大排序的,即最大元素位于隊列的前面。在插入元素時會插入到指定位置,確保隊內有序。(大根堆)
#include <iostream>
#include <queue>
using namespace std;
int main() {priority_queue<int> maxHeap;// 插入元素maxHeap.push(3);maxHeap.push(1);maxHeap.push(4);maxHeap.push(2);while (!maxHeap.empty()) {cout << maxHeap.top()<<" ";maxHeap.pop();}//4 3 2 1
}
#include <iostream>
#include <queue>
using namespace std;
int main() {priority_queue<int> maxHeap;// 插入元素maxHeap.push(3);maxHeap.push(1);maxHeap.push(4);maxHeap.push(2);隊列元素:4 3 2 1// 訪問隊頭元素(最大元素)cout << maxHeap.top();//4// 彈出隊頭元素maxHeap.pop();//4出//隊列元素:3 2 1// 再次訪問隊頭元素cout << maxHeap.top();//3// 獲取隊列中元素的數量cout << maxHeap.size();//3// 檢查隊列是否為空if (maxHeap.empty()) {cout << "Priority queue is empty." << endl;}else {cout << "Priority queue is not empty." << endl;}
}
小根堆
priority_queue<int, vector<int>, greater<int>> minHeap
(3)雙端隊列
#include <deque>
#include <iostream>
#include <deque>
using namespace std;
int main() {// 創建一個雙端隊列deque<int> deque;// 向雙端隊列的尾部添加元素deque.push_back(1);//隊列元素:1deque.push_back(2);//隊列元素:1(頭) 2(尾)// 向雙端隊列的頭部添加元素deque.push_front(3);//隊列元素:3 1 2deque.push_front(4);//隊列元素:4 3 1 2// 打印雙端隊列的元素for (int n : deque) {cout << n;}// 4 3 1 2// 從雙端隊列的尾部刪除元素deque.pop_back();//隊列元素:4 3 1// 從雙端隊列的頭部刪除元素deque.pop_front();//隊列元素:3 1
}
[例1] CLZ銀行問題
評測系統
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {int num;cin >> num;//操作數量queue<string> vipQueue;queue<string> normalQueue;for (int i = 0; i < num; ++i) {string operation,name;cin >> operation;if (operation == "IN") {cin >> name;char type;cin >> type;if (type == 'V') {vipQueue.push(name);}else {normalQueue.push(name);}}else {char type;cin >> type;if (type == 'V'&&!vipQueue.empty()) {vipQueue.pop();}else if(type=='N'&&!normalQueue.empty()) {normalQueue.pop();}}}while (!vipQueue.empty()) {cout << vipQueue.front()<<endl;vipQueue.pop();}while (!normalQueue.empty()) {cout << normalQueue.front() << endl;normalQueue.pop();}
}
[例2] 合并果子
評測系統
每次選擇兩個最小的數合并(貪心),并將合并后的新數重新放入堆中
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {int kind;cin >> kind;priority_queue<int, vector<int>, greater<int>> minHeap;for (int i = 0; i < kind; ++i) {int num;cin >> num;minHeap.push(num);}int sum = 0;while (minHeap.size() > 1) {int heapone=minHeap.top();minHeap.pop();int heaptwo = minHeap.top();minHeap.pop();sum += heapone + heaptwo;minHeap.push(heapone + heaptwo);}cout << sum;
}
[例3] 建筑搶修
評測系統
我們對建筑按照截止時間進行排序,并使用一個最大堆(優先隊列)來動態管理當前的修理計劃。每次當總修理時間超過當前考慮的建筑的截止時間時,我們從堆中移除修理時間最長的建筑。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct building {int repairtime;int deadline;
};
int cmp(building a, building b) {return a.deadline < b.deadline;
}
int main()
{int total = 0;int n;cin >> n;vector<building> a(n);for (int i = 0; i < n; ++i) {cin >> a[i].repairtime >> a[i].deadline;}sort(a.begin(), a.end(), cmp);priority_queue<int> q;for (int i = 0; i < n; i++) {q.push(a[i].repairtime);//一定修,因為馬上deadline了total += a[i].repairtime;if (total > a[i].deadline) {//如果超時,那么根據大根堆,隊列中維修時長最大的移除total -= q.top();q.pop();}}cout << q.size();return 0;
}
6.set
set存儲唯一元素,默認升序
#include <iostream>
#include <set>
using namespace std;int main() {set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(2); // 這個操作沒有效果,因為 2 已存在cout << "Set contains:";for (int x : s) {cout << " " << x;}cout << endl;//輸出:1 2 3 4
}
降序排列
#include <iostream>
#include <set>
using namespace std;int main() {set<int,greater<int>> s;//改為降序排列s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(2);cout << "Set contains:";for (int x : s) {cout << " " << x;}cout << endl;//輸出:4 3 2 1
}
multiset允許重復元素
#include <iostream>
#include <set>using namespace std;int main() {multiset<int> ms;ms.insert(3);ms.insert(1);ms.insert(4);ms.insert(2);ms.insert(2); // 可以插入重復元素// 輸出 multiset 的內容cout << "Multiset contains:";for (int x : ms) {cout << " " << x;}//輸出:1 2 2 3 4// 計算某個值在 multiset 中出現的次數int count = ms.count(2);cout <<count;//2
}
7.map
map存儲鍵值對,鍵是唯一的,鍵值對是根據鍵排序的(自動排序,默認升序排列),可以直接使用鍵訪問對應的值;在插入新元素時,若鍵已存在,則更新其對應的值
#include <iostream>
#include <map>
using namespace std;int main() {// 創建一個 mapmap<string, int> marks;// 插入鍵值對marks["Alice"] = 88;marks["Bob"] = 95;marks["Charlie"] = 72;// 更新鍵對應的值marks["Alice"] = 91;// 遍歷并打印 mapfor (const auto& pair : marks) {cout << pair.first << pair.second << endl;}/*輸出Alice91Bob95Charlie72*/// 查找并訪問元素if (marks.find("Bob") != marks.end()) {cout << marks["Bob"];//95}
}
8.練習
(1)寶藏排序
評測系統
#include <iostream>
#include<queue>
using namespace std;
int main() {int n;cin >> n;priority_queue<int,vector<int>,greater<int>> pq;while (n--) {int x;cin >> x;pq.push(x);}while(!pq.empty()) {cout<<pq.top()<<" ";pq.pop();}
}
(2)小藍吃糖果
評測系統
找出糖果數量最多的種類,其余糖果進行插空。
若最多種類的糖果數量是max,一共有max-1個空,第二大種類的糖果數一定不超過max-1,越插空越多,以此類推。只有當所有糖果加起來也沒有填滿max-1個空時,失敗。
#include <iostream>
#include <queue>
using namespace std;
int main() {int n;cin >> n;long long int total=0;priority_queue<int> a;for (int i = 0; i < n; i++) {int x;cin >> x;a.push(x);total += x;}int max = a.top();total -= max;if (max - 1 <= total)cout << "Yes";elsecout << "No";
}
(3)小藍的括號串
評測系統
#include <iostream>
#include <stack>
using namespace std;
int main() {stack<char> s;int n;cin >> n;while (n--) {char x;cin >> x;if (x == '(') {s.push(x);}else {if (!s.empty()) {s.pop();}else {cout << "No";return 0;}}}if (!s.empty()) {cout << "No";}else {cout << "Yes";}
}
(4)快遞分揀
評測系統
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {int n;cin >> n;map<string, vector<string>> m;//一對多的關系,一個鍵對應多個值vector<string> vm;//記錄城市出現順序while (n--) {string s, p;cin >> s >> p;if (m.find(p) == m.end()) {//當前城市首次出現,可改為if(m.count(p)==0)vm.push_back(p);}m[p].push_back(s);}for (const auto& x : vm) {cout << x <<" " << m[x].size() << endl;for (const auto& x2 : m[x]) {cout << x2 << endl;}}
}
(5)順子日期
答案:14
#include<iostream>
#include<string>
using namespace std;
int panduanmonth(int x) {if (x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12)return 31;else if (x == 4 || x == 6 || x == 9 || x == 11)return 30;else {return 28;}
}
string formatDate(int a, int b, int c) {string s = "2022";if (b < 10) {s+= "0"+to_string(b);}else {s+= to_string(b);}if (c < 10) {s += "0" + to_string(c);}else {s += to_string(c);}return s;
}
bool isSequentialDate(string s) {for (int i = 0; i <= 5; ++i) {if (s[i] + 1 == s[i + 1] && s[i + 1] + 1 == s[i + 2])return true;}return false;
}
int main() {int count = 0;for (int month = 1; month <= 12; month++) {for (int day = 1; day <= panduanmonth(month); day++) {string date = formatDate(2022, month, day);if (isSequentialDate(date)) {count++;}}}cout << count;
}
(6)小明和完美序列
評測系統
對于序列中的每個數字,計算它出現的次數。比較其值和出現的次數。如果出現次數大于數字的值,則需要刪除多余的出現。如果出現次數小于數字的值,則需要全部刪除。計算總共需要刪除的數字數量。
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main() {int n;cin >> n;map<int, int> count;int num;for (int i = 0; i < n; ++i) {cin >> num;count[num]++;}int deletecount = 0;for (const auto& x : count) {int a = x.first;int b = x.second;if (a > b) {deletecount += b;}else if (a < b) {deletecount += b - a;}}cout << deletecount;
}