二分查找
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;
}