C++【STL】集合set

標準庫提供 set 關聯容器分為：

按關鍵字有序保存元素：set（關鍵字即值，即只保存關鍵字的容器）、multiset（關鍵字可重復出現的 set）；
無序集合：unordered_set（用哈希函數組織的 set）、unordered_multiset（用哈希函數組織的 set，關鍵字可以重復出現）。

  ----集合--set：----------集合三要素----------------------------特點----------set---------multiste-----------unordered_set確定性 ? ? ? ?YES ? ? ? ? ? ?YES ? ? ? ? ? ? ? YES互異性 ? ? ? ?YES ? ? ? ? ? ?NO ? ? ? ? ? ? ? ?YES無序性 ? ? ? ?NO ? ? ? ? ? ? NO ? ? ? ? ? ? ? ?YES------------------------------------------------------------

優點：自動排序，自動去重?

set的定義

    set<類型名> 變量名;

同樣也可以定義set數組。

    set<int> arr[10];

?set的遍歷

for(set<int>::iterator it=se.begin();it!=se.end();it++){if(sign){cout<<*it;sign=0;}else{cout<<' '<<*it;}}

注意：除了 vector 和 string 以外的 STL 容器都不支持 *(it + i) 的訪問方式

?常見操作

插入元素：數組名.insert();unordered_set時間復雜度為O(1)，set為O(log N);
刪除元素：數組名.erase();
查找元素：數組名.find()-----也可以用：數組名.count()會返回查找元素的個數
查看大小：數組名.size()
判空 ? ?：數組名.empty()
清空 ? ?：數組名.clear()

常見操作具體用法：內容參考?

由于set的用處并不是經常考，一些單一用set的題目過于簡單，寫上去有點太水了，因為我發誓以后不寫水博客了，所以以后有更好的用搭配set優化的題目我再補充。

【算法】常見二分

下面來總結一下二分的板子：

為了方便以后的比賽整理模板，今天就先把二分的模板整理到這里了，有同樣需求的小伙伴直接收藏即可。

二分查找：

使用前提：數組有序排列

參數為起始迭代器、終止迭代器以及給定元素值

lower_bound()?：返回第一個大于等于給定元素的位置

upper_bound()：返回第一個小于給定元素的位置

用法

?1.查找元素是否存在：

bool check(vector<int>& v, int value) {auto it = lower_bound(v.begin(), v.end(), value);return it != v.end() && *it == value;
}

2.向有序數組中插入元素：

void insert_to_sorted(vector<int>& v, int value) {auto pos = lower_bound(v.begin(), v.end(), value);v.insert(pos, value);
}

?

3.查找范圍：

auto range = equal_range(v.begin(), v.end(), value);
// 等同于:
auto low = lower_bound(v.begin(), v.end(), value);
auto up = upper_bound(v.begin(), v.end(), value);

二分答案：

二分答案是一種對答案進行二分查找的算法，適用于滿足以下條件的問題：

問題的答案具有單調性（隨著某個變量的增大，結果單調遞增或遞減）

可以相對容易地驗證某個候選答案是否可行

與傳統的二分查找比較：

二分答案的模板有很多，我會總結出我經常用到的一種：

首先是整數二分答案模板：

整形二分

如果求的是最大的最小值（滿足條件的最大值，較靠右端的答案）可以用(l+r+1)>>1;

如果是求最小的最大值（滿足條件的最小值，較靠左端的答案），可以用(l+r)>>1;

int l=1,r=1e18;while(l<r){int mid = (l+r+1)>>1;if(check(mid)) l = mid(r = mid);//更新左/右邊界else r = mid-1(l = mid + 1);//更新左/右邊界}cout<<l<<endl;

二分答案難就難在check函數的編寫，check函數顧名思義就是把當前的mid（可能的答案值）代入問題中看是否符合要求 。

有了理論和模板，下面就是不斷的練習了：

進擊的奶牛

這道題題目意思讀不懂，但是和跳石頭差不多，直接寫就行了。

check函數的難點在于需要用一個變量來存儲上一個選擇的位置。

// Problem: P1824 [USACO05FEB] 進擊的奶牛 Aggressive Cows G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1824
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e5+10;
int a[N];
int n,m;bool check(int mid)
{int num=1;int f=1;for(int i=2;i<=n;i++){if(a[i] - f >= mid){num++;f = a[i];}}return num>=m;
}void solve()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);int l=1,r=1e18;while(l<r){int mid = (l+r+1)>>1;if(check(mid)) l = mid;else r = mid-1;}cout<<l<<endl;
}signed main()
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

推薦練習題：

1、跳石頭

2、砍樹

3、冶煉金屬

浮點型二分

這中類型題的模板也有很多，有的是在給定的誤差范圍內進行微調，有的是判斷條件進行誤差分析并通過浮點數自身的精確度來調整答案，其中一種個人認為比較保險的是下面的這種：

double l = 0,r = 1e18;while(r - l > 1e-5){double mid = (l + r) / 2.0;if(check(mid)) l = mid;else r = mid;}

有了模板，難點同樣成為了check函數的編寫。。。

來看題目：
切繩子

這是一道基礎的題目，check函數很好想出來，這道題的難點反而成為了浮點二分答案的記憶

?只需要遍歷一遍看能切出來多少條繩子即可。

// Problem: P1577 切繩子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1577
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
int n,k;
const int N = 10010;
double a[N];
bool check(double mid)
{int num=0;for(int i=1;i<=n;i++){num += (int)(a[i] / mid);}	return num>=k;
}void solve()
{cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];double l = 0,r = 1e18;while(r - l > 1e-5){double mid = (l + r) / 2.0;if(check(mid)) l = mid;else r = mid;}printf("%.2f",l);
}signed main()
{// IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

推薦練習題：

最佳牛圍欄。

總結：

今天是第五天了，這周就屬今天最輕松了，之后這周末我會整理整理這周所學的內容，我們下周見！