2024/2/29 备战蓝桥杯 6-1 二分

目录

查找

【深基13.例1】查找 - 洛谷

数对

A-B 数对 - 洛谷

砍树

[COCI 2011/2012 #5] EKO / 砍树 - 洛谷

---

参考连接：AcWing 789. 数的范围---二分法一次搞懂 - AcWing

1.程序中不要同时出现l = mid, r = mdi这两条语句。

2.如过程序中出现了l = mid，mid的值用 (l + r + 1) / 2计算。

3.如果程序中出现了r = mid，mid的值用（(l + r) / 2计算。
 

大佬给的方法：

两种写法：
r = mid ,l = mid+1     此时写（l + r ) / 2            (答案在左边)
l = mid , r=mid-1      此时写（l + r + 1) /2           （答案在右边）

查找

【深基13.例1】查找 - 洛谷

完整代码:

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 1e6+10;
std::vector<int> a(N+1);
int n,m;
int check(int y)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;if(a[mid]>=y) r=mid;else l=mid+1;}if(a[l]==y) return l;else return -1;
}
signed main()
{std::cin >> n >> m;for(int i = 1;i <= n;i ++){std::cin >> a[i];}while(m --){int x;std::cin >> x;std::cout<<check(x)<<" ";}return 0;
}

数对

A-B 数对 - 洛谷

这个我没有用二分写，而是用map映射

完整代码：

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 2e5+10;
signed main()
{int n,c;std::cin >> n >> c;std::vector<int> a(n+1);std::map<int,int> mp;for(int i = 1;i <= n;i ++){std::cin >> a[i];mp[a[i]]++;}int ans=0;for(int i = 1;i <= n;i ++){ans+=mp[a[i]-c];}std::cout<<ans;return 0;
}

砍树

[COCI 2011/2012 #5] EKO / 砍树 - 洛谷

太难了这道题写了一下午才写出来

完整代码：

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 1e6+10;
int a[N];
int n,m;
bool check(int x)
{int sum=0;for(int i = 1;i <= n;i ++){if(a[i]>x)sum+=(a[i]-x);}if(sum>=m)return true;elsereturn false;
}
signed main()
{std::cin >> n >> m;for(int i = 1;i <= n;i ++){std::cin >> a[i];}std::sort(a+1,a+1+n);int l=a[1],r=a[n];while(l < r){int mid = (l+r+1)/2;if(check(mid))l=mid;elser=mid-1;}std::cout<<l;return 0;
}