文章目录
二分查找
1.查找大于等于x的最小值
#include<iostream> using namespace std; const int MAXN = 1e6 + 7; int num[MAXN]; int n; int binary(int x) { int ans = -1;//-1说明ans不存在 int left = 0, right = n - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (num[mid] >= x) { ans = num[mid]; right = mid - 1; } else left = mid + 1; } return ans; } int main() { int x; cin >> n >> x; for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } cout << binary(x) << endl; return 0; }
查找重复数组中x的最小下标
int binaryindex(int x) { int ans = -1; int left = 0, right = n - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (num[mid] >= x) { ans =mid; right = mid - 1; } else left = mid + 1; } return ans; } int main() { int x; cin >> n >> x; for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } if (num[binaryindex(x)] == x)//判断找到的下标对应的值是否是x { cout << binaryindex(x) << endl; } return 0; }
二分答案
这些值 1 2 3 4 5 6 7
对应 1 1 1 1 0 0 0 要找到符合条件的最大值
进击的奶牛
link.
题目描述
Farmer John 建造了一个有 N(2<=N<=1000000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1x_1x1 ,…,xNx_NxN(0<xi<1000000000),他的c（2<c<n）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢?
输入格式
第 1 行：两个用空格隔开的数字 N 和 C。
第 2 ~ N+1 行：每行一个整数，表示每个隔间的坐标
输出格式
输出只有一行，即相邻两头牛最大的最近距离。
输入
5 3
1
2
8
4
9
输出
3
计算最大的最近距离
1.再dis下可以放几头牛（首先先排序）
2.判断是否等于c
3.用二分法找到最小值
#include<iostream> using namespace std; int N, C; const int MAXN = 1e7 + 6; int arr[MAXN]; int comp(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int coutcow(int dis) { int now = arr[0]; int i = 1; int cnt = 1; for (i = 1; i < N; i++) { if (arr[i] - now >= dis) { cnt++; now = arr[i]; } } return cnt; } bool beyondC(int dis) { return coutcow(dis) >= C; } int binary() { int left = 1, right = 1e9; int ans = -1; int mid; while (left <= right) { mid = (left + right) / 2; if (beyondC(mid)) { ans = mid; left = mid + 1; } else right = mid - 1; } return ans; } int main() { cin >> N >> C; int i = 0; for (i = 0; i < N; i++) { scanf("%d", &arr[i]); } qsort(arr, N, sizeof(int), comp); cout << binary() << endl; return 0; }
皮皮的糖果
皮皮有n包不同口味的糖果，分给每个人糖果的 数量必须相等，并且每个人只能有一种口味，也就是说，可以把一包糖分给多个人，但是一个人的糖不能有多少口味，每个人最多能分到几颗糖
#include<iostream> using namespace std; const int MAXN = 1e6 + 7; int arr[MAXN]; int n, m; int count(int b) { int sum = 0; int i = 0; for (i = 0; i < n; i++) { sum += arr[i] / b;//sum计算在分b个糖果的情况下可有多少个人 } return sum; } bool check(int b,int m) { return count(b) >= m; } int binary(int& n, int& m) { int left = 1, right = 1e6; int mid; int ans = 1; while (left <= right) { mid = (left + right) / 2; if (check(mid,m)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } return ans; } int main() { //n种口味，m个人 int t; cin >> t ; while (t--) { cin >> n >> m; int i = 0; for (i = 0; i < n; i++) { scanf("%d", &arr[i]); } int min = arr[0]; cout<<binary( n, m)<<endl; } return 0; }
