二分法
简介：
网上模板很多，看得眼花缭乱，搞得不知道用哪种好，我自己就用这种吧，这是前几天看那道冶炼金属那题看到得模板，这个模板应该也适用于很多题了(闭区间)
- 寻找靠左的数
while(lr)
{
int mid=l+((r-l)>>1);
if(a[mid]>=x)r=mid-1;
else l=mid+1;
}
if(a[l]==x)return l;
else return -1;
由上面的图示可以看成，如果是寻找左边的数最终的while(l，因此q[l]==x,那么我们就找到了我们想要且靠左的数的位置
- 寻找靠右的数
while(lr)
{
int mid=l+((r-l)>>1);
if(a[mid]x)l=mid+1;
else r=mid-1;
}
if(a[r]==x)return r;
else return -1;
由这个图示可知，如果要寻找右边的数，最终while(l
例题:
【洛谷】P1102 A-B 数对
A-B 数对
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数
C
C
C，要求计算出所有满足
A
−
B
=
C
A – B = C
A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数
N
,
C
N,C
N,C。
第二行，
N
N
N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足
A
−
B
=
C
A – B = C
A−B=C 的数对的个数。
样例 #1
样例输入 #1
4 1
1 1 2 3
样例输出 #1
3
提示
对于
75
%
75%
75% 的数据，
1
≤
N
≤
2000
1 leq N leq 2000
1≤N≤2000。
对于
100
%
100%
100% 的数据，
1
≤
N
≤
2
1
0
5
1 leq N leq 2 times 10^5
1≤N≤2105，
0
≤
a
i
0≤ai230，
1
≤
C
1≤C230。
2017/4/29 新添数据两组
思路：
这题先走了个弯路，即排序后，先打算固定一个数，然后看后面的数减去前面的数，如果等于c，则记一次数，然而这种方法就是常说的暴力法，数据量大的时候会超时，我们的计算机1s内能算1e7次到1e8次，超过这个数必然超时了
因此正解是利用二分，先移项，A=B+C,C是固定的，那么我们去遍历数组，数组的每一项都在每一次循环作为B,然后加上C的得到数A,然后在去数组中寻找A的位置，找到1个加入答案，没找到就不加，注意二分一定要先排序排序排序，还有就是我们在数据范围很大的时候一定要开long long ，如果判断不准，那就开着long long
#include
using namespace std;
typedef long long LL;
LL sum=0;
LL bserach1(LL q[],LL n,LL a)
{
LL l=0,r=n-1;
LL mid=l+r>>1;
while(lr)
{
mid=l+r>>1;
if(q[mid]>=a){r=mid-1;}
else l=mid+1;
}
if(q[l]==a)return l;
else return -1;
}
LL bserach2(LL q[],LL n,LL a)
{
LL l=0,r=n-1;
LL mid=l+r>>1;
while(lr)
{
mid=l+r>>1;
if(q[mid]a){l=mid+1;}
else r=mid-1;
}
if(q[r]服务器托管==a)return r;
else return -1;
}
int main()
{
LL n=0,c=0;LL q[1000000]={0};
cin>>n>>c;
for(LL i=0;in;i++)cin>>q[i];
sort(q,q+n);
LL res1=0,res2=0;
for(LL i=0;in;i++)
{
LL a=q[i]+c;
res1=bserach1(q,n,a);
if(res1==-1)continue;
else
{
res2=bserach2(q,n,a);
}
sum+=(res2-res1+1);
}
coutsum;
return 0;
}
交完后发现#4 RE了，一直不知道为什么，后来问了学长才知道是初始化的原因。
RE的错误点一般是在和溢出有关，数组溢出，还有就是未初始化，未初始化这个数可能会很大，导致溢出
所以注意一定要初始化！！！初始化！！！初始化！！！
[蓝桥杯 2023 省 B] 冶炼金属
[蓝桥杯 2023 省 B] 冶炼金属
题目描述
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性
V
V
V，
V
V
V 是一个正整数，这意味着消耗
V
V
V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足
V
V
V 时，无法继续冶炼。
现在给出了
N
N
N 条冶炼记录，每条记录中包含两个整数
A
A
A 和
B
B
B，这表示本次投入了
A
A
A 个普通金属 O，最终冶炼出了
B
B
B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这
N
N
N 条冶炼记录，请你推测出转换率
V
V
V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数
N
N
N，表示冶炼记录的数目。
接下来输入
N
N
N 行，每行两个整数
A
,
B
A,B
A,B，含义如题目所述。
输出格式
输出两个整数，分别表示
V
V
V 可能的最小值和最大值，中间用空格分开。
样例 #1
样例输入 #1
3
75 3
53 2
59 2
样例输出 #1
20 25
提示
【样例说明】
当
V
=
20
V=20
V=20 时，有：
⌊
75
20
⌋
=
3
,
⌊
53
20
⌋
=
2
,
⌊
59
20
⌋
=
2
leftlfloorfrac{75}{20}rightrfloor=3,leftlfloorfrac{53}{20}rightrfloor=2,leftlfloorfrac{59}{20}rightrfloor=2
⌊2075⌋=3,⌊2053⌋=2,⌊2059⌋=2，可以看到符合所有冶炼记录。
当
V
=
25
V=25
V=25 时，有：
⌊
75
25
⌋
=
3
,
⌊
53
25
⌋
=
2
,
⌊
59
25
⌋
=
2
leftlfloorfrac{75}{25}rightrfloor=3,leftlfloorfrac{53}{25}rightrfloor=2,leftlfloorfrac{59}{25}rightrfloor=2
⌊2575⌋=3,⌊2553⌋=2,⌊2559⌋=2，可以看到符合所有冶炼记录。
且再也找不到比
20
20
20 更小或者比
25
25
25 更大的符合条件的
V
V
V 值了。
【评测用例规模与约定】
对于
30
%
30 %
30% 的评测用例，
1
≤
N
≤
1
0
2
1 leq N leq 10^{2}
1≤N≤102。
对于
60
%
60 %
60% 的评测用例，
1
≤
N
≤
1
0
3
1 leq N leq 10^{3}
1≤N≤103。
对于
100
%
100 %
100% 的评测用例，
1
≤
N
≤
1
0
4
1 leq N leq 10^{4}
1≤N≤104，
1
≤
B
≤
A
≤
1
0
9
1 leq B leq A leq 10^{9}
1≤B≤A≤109。
蓝桥杯 2023 省赛 B 组 C 题。
==思路:==这题用二分是可行的,用两次二分，一次寻找靠左边的数，即我们的vmin，另一次则寻找靠右边的数，即我们的vmax
#include
using namespace std;
const int N = 1e4 + 5;
int n;
int a[N], b[N];
bool check1(int v)
{
for (int i = 0;服务器托管 i n; i++)
{
if (a[i] / v > b[i])return false;
}
return true;
}
bool check2(int v)
{
for (int i = 0; i n; i++)
{
if (a[i] / v b[i])return false;
}
return true;
}
int main()
{
cin >> n;
for (int i = 0; i n; i++)cin >> a[i] >> b[i];
int l = 0, r = 1e9, vmin = 0, vmax = 0;
while (l r)
{
int mid = l + ((r - l) >> 1);
if (check1(mid)) { vmin = mid; r = mid - 1; }
else l = mid + 1;
}
l = 1, r = 1e9;
while (l r)
{
int mid = l + ((r - l) >> 1);
if (check2(mid)) { vmax = mid; l = mid + 1; }
else r = mid - 1;
}
cout vmin " " vmax;
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
Xilinx 7系列FPGA配置（ug470） 配置模式 串行配置模式 接口 从-连接方式 主-连接方式 串行菊花链（非同时配置） 串行配置（同时配置） 时序 主SPI配置模式 SPIx1/x2 连接图 SPIx1模式时序 SPIx4 连接图 SPI操作指令 …
