Set 二分 -＞ 剑指算法竞赛
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;
}
推荐练习题：
最佳牛围栏。
总结：
今天是第五天了，这周就属今天最轻松了，之后这周末我会整理整理这周所学的内容，我们下周见！