log算法

文章目录

• 二分查找
• • 1.查找大于等于x的最小值
  • 查找重复数组中x的最小下标
• 二分答案
• • 进击的奶牛

二分查找

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;
}