整数二分模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
(1)、数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
int n,t,x;
int q[N];
int main()
{
scanf("%d%d",&n,&t);
for(int i=0;i<n;i++)
{
scanf("%d",&q[i]);
}
while(t--)
{
scanf("%d", &x);
int l,r;
l=0;r=n-1;
int mid;
while(l<r)
{
mid=l+r >>1;
if(q[mid]>=x)
{
r=mid;
}
else
{
l=mid+1;
}
}
if(q[r]==x)
{
printf("%d ",r);
r=n-1;
while(l<r)
{
mid=(l+r+1) /2;
if(q[mid]<=x)
{
l=mid;
}
else
{
r=mid-1;
}
}
printf("%d \n",r);
}
else
{
printf("-1 -1\n");
}
}
return 0;
}
（2）、机器人跳跃问题
机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。
编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑高度为 H(i) 个单位。
起初，机器人在编号为 0 的建筑处。
每一步，它跳到下一个（右边）建筑。
假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。
如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值。
游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
输入格式
第一行输入整数 N。
第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。
输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
数据范围
1≤N,H(i)≤105,
输入样例1：
5
3 4 3 2 4
输出样例1：
4
输入样例2：
3
4 4 4
输出样例2：
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int q[N];
int n;
bool check(int e)
{
for (int i = 0; i <n; i ++ )
{
e = e * 2 - q[i];
if (e >= 1e5) return true;
if (e < 0) return false;
}
return true;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
int l = 0, r = 1e5;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}
总结：1.由题意知不管下一个建筑物的高度是否高于现有能量能量的变化总为2*e-H[i];
2.最优值问题，能量有明确的范围，故使用二分，将最优解问题转化为判断问题；
（3）分巧克力
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
形状是正方形，边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105,
1≤Hi,Wi≤105
输入样例：
2 10
6 5
5 6
输出样例：
2
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, k;
int h[N], w[N];
bool check(int a)
{
int res=0;
for(int i=0;i<n;i++)
{
res+=(h[i]/a)*(w[i]/a);
if(res>=k)return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d%d",&h[i],&w[i]);
}
int l=1,r=1e5;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
cout<<l;
return 0;
}
（4）四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗106
输入样例：
5
输出样例：
0 0 1 2
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2500010;
struct Sum
{
int s, c, d;
bool operator< (const Sum &t)const
{
if (s != t.s) return s < t.s;
if (c != t.c) return c < t.c;
return d < t.d;
}
}sum[N];
int n, m;
int main()
{
cin >> n;
for (int c = 0; c * c <= n; c ++ )
for (int d = c; c * c + d * d <= n; d ++ )
sum[m ++ ] = {c * c + d * d, c, d};
sort(sum, sum + m);
for (int a = 0; a * a <= n; a ++ )
for (int b = 0; a * a + b * b <= n; b ++ )
{
int t = n - a * a - b * b;
int l = 0, r = m - 1;
while (l < r)
{
int mid = l + r >> 1;
if (sum[mid].s >= t) r = mid;
else l = mid + 1;
}
if (sum[l].s == t)
{
printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
return 0;
}
}
return 0;
}
总结：空间换时间，先枚举c，d存起来，最下面的后面循环a,b去找满足要求的n-aa-bb
(5)最佳牛围栏
农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛，其数量不会少于 1 头，也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N 和 F，数据间用空格隔开。
接下来 N 行，每行输入一个整数，第 i+1 行输入的整数代表第 i 片区域内包含的牛的数目。
输出格式
输出一个整数，表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。
数据范围
1≤N≤100000
1≤F≤N
输入样例：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
6500
代码：
#include <cstdio>
#include <iostream>
const int N = 100005;
int cows[N]; double sum[N];
int n, m;
bool check(double avg) {
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + cows[i] - avg;
}
double minv = 0;
for (int i = 0, j = m; j <= n; j++, i++) {
minv = std::min(minv, sum[i]);
if(sum[j] - minv >= 0) return true;
} return false;
}
int main() {
scanf("%d %d", &n, &m);
double l = 0, r = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &cows[i]);
r = std::max(r, (double)cows[i]);
}
while(r - l > 1e-5) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
} printf("%d\n", (int)(r * 1000));
return 0;
}
①：我们要找的是 有没有一段不小于F的区间，使这段区间的平均数尽可能的大，如果我们找到了一段连续的区间且区间长度不小于F且平均数大于我们二分的平均数 那么大于这个数且区间也满足的一定满足了 我们直接判断正确即可
②：因为我们要找一段区间的平均数，根据平均数的一个基本应用，显而易见，对于一段序列，每个数减去我们所算的平均数，如果大于0 那么他本身就大于平均数，如果小于0 那么它本身就小于平均数 此时我们就能算出哪些数大于0 哪些数小于0 ，之后我们再使用前缀和，就能判断一个区间内的平均值是否大于或小于我们二分的平均数了
③：据②我们还可以继续优化，因为我们不仅需要找F大小区间内，我们还要找＞F大小区间内的，我们如果用二次for太费时间了，我们这里可以使用双指针的做法，我们设i=0,j=Fi=0,j=F 每次使两个数++ 因为i,ji,j始终满足相距FF的距离，所以我们用一个变量minvminv来存储ii所遍历到的最小值，这样我们比较的距离一定是≥F≥F的，并且如果我们用jj位的前缀和数减去minvminv的话，就能得到我们的最优解，如果这个最优解＞= 0 那么就满足我们的指定条件（如果不懂这一步 请看②）。 到此，结束
我们便可以写出二分的checkcheck代码
bool check(double avg) {
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + (cows[i] - avg); //计算前缀和
}
double minv = 0; //设置最小值
for (int i = 0, j = m; j <= n; j++, i++) {
minv = std::min(minv, sum[i]); //找最优极小值
if(sum[j] - minv >= 0) return true; //进行判断
} return false; //如果所有的都不满足，那么这个平均数就一定不满足
}
作者：Nicoppa
链接：https://www.acwing.com/solution/content/1148/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
（1）剪绳子
有 N 根绳子，第 i 根绳子长度为 Li，现在需要 M 根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。
输入格式
第一行包含 2 个正整数 N、M，表示原始绳子的数量和需求绳子的数量。
第二行包含 N 个整数，其中第 i 个整数 Li 表示第 i 根绳子的长度。
输出格式
输出一个数字，表示裁剪后最长的长度，保留两位小数。
数据范围
1≤N,M≤100000,
0<Li<109
输入样例：
3 4
3 5 4
输出样例：
2.50
样例解释
第一根和第三根分别裁剪出一根 2.50 长度的绳子，第二根剪成 2 根 2.50 长度的绳子，刚好 4 根。
代码：
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
bool check(double mid)
{
int cnt = 0;
for (int i = 0; i < n; i ++ )
cnt += w[i] / mid;
return cnt >= m;
}
int main()
{
cin >> n >> m;
for (int i = 0; i <n; i ++ ) cin >> w[i];
double l = 0, r = 1e9;
while (r - l > 1e-4)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", r);
return 0;
}
浮点数二分：
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
(1)数的三次方根
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
代码：
#include <iostream>
using namespace std;
int main()
{
double x;
cin >> x;
double l = -100, r = 100;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%.6lf\n", l);
return 0;
}
1、0到n-1中缺失的数字
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1 之内。
在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
数据范围
1≤n≤1000
样例
输入：[0,1,2,4]
输出：3
代码：
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] != mid) r = mid;
else l = mid + 1;
}
if (nums[r] == r) r ++ ;
return r;
}
};
(2)寻找峰值
峰值定义为比左右相邻元素大的元素。
给定一个长度为 n 的数组 nums，数组下标从0开始，保证 nums[i]≠nums[i+1]，请找出该数组的峰值，并返回峰值的下标。
数组中可能包含多个峰值，只需返回任意一个即可。
假定 nums[-1] = nums[n] = -∞。
本题中数组是隐藏的，你可以通过我们预设的 int 函数 query 来获得数组中某个位置的数值是多少。
例如，query(a) 即可获得下标为 a 的元素的值。
注意：
query 函数的调用次数不能超过 min(3×⌈log2n⌉,10)。
数据范围
1≤n≤105，
数组中的整数在 int 范围内。
输入样例1：
[1, 2, 3, 1]
输出样例1：
2
输入样例2：
[1, 2, 1, 3, 5, 6, 4]
输出样例2：
1
样例解释
对于样例 1，3 是峰值，其下标为 2。
对于样例 2，2 和 6 是峰值，下标为 1 和 5，输出任意一个均可。
代码：
// Forward declaration of queryAPI.
// int query(int x);
// return int means nums[x].
class Solution {
public:
int findPeakElement(int n) {
int l=0;
int r=n-1;
while(l<r)
{
int mid=l+r >>1;
if(query(mid)>=query(mid+1))r=mid;
else l=mid+1;
}
return r;
}
};
2、 不修改数组找出重复的数字
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
数据范围
1≤n≤1000
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？
代码：
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l=1;
int r=nums.size()-1;
while(l<r)
{
int mid = l+r>>1;
int s=0;
for(auto x:nums)
{
if(x>=l&&x<=mid)
{
s+=1;
}
}
if(s>mid-l+1)
{
r=mid;
}
else l=mid+1;
}
return r;
}
};
3、防线
达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天......受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。
就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。
数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。
由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。
但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。
防线由很多防具组成，这些防具分成了 N 组。
我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。
也就是说，我们可以用三个整数 S， E 和 D 来描述一组防具，即这一组防具布置在防线的 S，S+D，S+2D，…，S+KD(K∈Z，S+KD≤E，S+(K+1)D>E)位置上。
黑化的怪兽达达设计的防线极其精良。
如果防线的某个位置有偶数个防具，那么这个位置就是毫无破绽的(包括这个位置一个防具也没有的情况，因为 0 也是偶数)。
只有有奇数个防具的位置有破绽，但是整条防线上也最多只有一个位置有奇数个防具。
作为行动队的队长，lqr 要找到防线的破绽以策划下一步的行动。
但是，由于防具的数量太多，她实在是不能看出哪里有破绽。
作为 lqr 可以信任的学弟学妹们，你们要帮助她解决这个问题。
输入格式
输入文件的第一行是一个整数 T，表示有 T 组互相独立的测试数据。
每组数据的第一行是一个整数 N。
之后 N 行，每行三个整数 Si，Ei，Di，代表第 i 组防具的三个参数，数据用空格隔开。
输出格式
对于每组测试数据，如果防线没有破绽，即所有的位置都有偶数个防具，输出一行 “There’s no weakness.”(不包含引号) 。
否则在一行内输出两个空格分隔的整数 P 和 C，表示在位置 P 有 C 个防具。当然 C 应该是一个奇数。
数据范围
防具总数不多于108,
Si≤Ei,
1≤T≤5,
N≤200000,
0≤Si，Ei，Di≤231−1
输入样例：
3
2
1 10 1
2 10 1
2
1 10 1
1 10 1
4
1 10 1
4 4 1
1 5 1
6 10 1
输出样例：
1 1
There’s no weakness.
4 3
代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
struct Seq
{
int s, e, d;
}seqs[N];
LL get_sum(int mid)
{
LL res=0;
for(int i=0;i<n;i++)
{
if(seqs[i].s<=mid)
{
res += (min(seqs[i].e, mid) - seqs[i].s) / seqs[i].d + 1;
}
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int l=0,r;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int s, e, d;
scanf("%d%d%d", &s, &e, &d);
seqs[i] = {s, e, d};
r = max(r, e);
}
while (l < r)
{
int mid = (LL)l + r >> 1;
if (get_sum(mid) & 1) r = mid;
else l = mid + 1;
}
auto sum = get_sum(r) - get_sum(r - 1);
if (sum % 2) printf("%d %lld\n", r, sum);
else puts("There's no weakness.");
}
return 0;
}
总结：
算法：前缀和 + 二分位置
1、奇数位存在性
整个序列中至多有一个位置的数字所占数量是奇数，所以如果存在奇数位，则整个数列的总和必然是奇数（奇数 + 偶数 = 奇数，偶数 + 偶数 = 偶数）。反之，若不存在奇数位，则一定是偶数。故只需判断数字数量的总和的奇偶性即可。
2、二分位置
若存在这个奇偶性，我们可以通过二分答案的位置来找到这个位置，然后判断区间[l,mid][l,mid]的总和的奇偶性。若为奇数，则奇数位存在于此区间。反之若为偶数，则一定存在于[mid+1,r][mid+1,r]区间。用这个方法逐步缩小范围即可。
关于查找[l,mid][l,mid]的总和，我们可以用前缀和的思路，用sum[mid]−sum[l−1]sum[mid]−sum[l−1]即可求出。(sum[i]sum[i]为求出ii位置之前所有位置的和)
3、O(n)O(n)时间求出区间sum[x]sum[x]的数字个数
设整个数列的最小位置为minnminn
这里，我们枚举每一个等差数列（它的起点为ss，终点为ee，差为dd）。若s<=xs<=x，则两区间存在交集。
则它与[minn,x][minn,x]的共同区间为[s,min(e,x)][s,min(e,x)]。那么此区间包含此数列的个数是⌊(min(e,x)−s)/d⌋+1⌊(min(e,x)−s)/d⌋+1。
正确性证明十分容易：
在此区间中存在一段区间，共⌊s,min(e,x)/d⌋∗d⌊s,min(e,x)/d⌋∗d个位置，头尾的位置上都有数字，差为dd，则数字的数量就是⌊(min(e,x)−s)/d⌋+1⌊(min(e,x)−s)/d⌋+1。
时间复杂度：O(nlogn)O(nlogn)
二分的时间为O(logn)O(logn)，每次check()check()的时间为O(n)O(n)，故总的时间复杂度为O(nlogn)O(nlogn)。
作者：墨染空
链接：https://www.acwing.com/solution/content/2545/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
跳石头 （同下一题）
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。
组委会已经选择好了两块岩石作为比赛起点和终点。
在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。
在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。
由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数 Di（0 < Di < L） 表示第 i 块岩石与起点的距离。
这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
输出文件只包含一个整数，即最短跳跃距离的最大值。
数据范围
0≤M≤N≤50000,
1≤L≤109
输入样例：
25 5 2
2
11
14
17
21
输出样例：
4
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int L,n,m;
const int N = 50010;
int w[N];
bool check(int mid)
{
int cnt=0;
int ans=0;
for(int i=1;i<=n;i++)
{
if(w[i]-cnt<mid)ans++;
else cnt=w[i];
}
return ans<=m;
}
int main()
{
cin>>L>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
w[++n]=L;
int l=1;
int r=1e9;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
总结：
如果长度 LenLen 可以满足，那么当长度小于 LenLen 时也可以满足，所以我们可以二分出最大的 LenLen。
剩下的问题是如何判断给定 LenLen 的情况下，能否最多拿走 MM 块石头，使得所有相邻两块石头之间的距离不小于 LenLen。
这一步可以贪心来做。从前往后扫描，并记一下上一块石头的位置。
如果当前石头和上一块石头的距离小于 LenLen，则将当前石头拿走。这里给出证明：如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。
如果当前石头和上一块石头的距离大于等于 LenLen，则将上一块石头更新成当前这块。
扫描结束后判断拿走的石头数量是否小于等于 MM。
时间复杂度分析
总共二分 O(logL)O(logL) 次，每次贪心的计算是 O(N)O(N)，因此总时间复杂度是 O(NlogL)O(NlogL)。
愤怒的牛（同下一题，小区别）
农夫约翰建造了一座有 n 间牛舍的小屋，牛舍排在一条直线上，第 i 间牛舍在 xi 的位置，但是约翰的 m 头牛对小屋很不满意，因此经常互相攻击。
约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。
也就是要最大化最近的两头牛之间的距离。
牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。
为了不让牛互相伤害。
约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？
输入格式
第一行用空格分隔的两个整数 n 和 m；
第二行为 n 个用空格隔开的整数，表示位置 xi。
输出格式
输出仅一个整数，表示最大的最小距离值。
数据范围
2≤n≤105,
0≤xi≤109,
2≤m≤n。
输入样例：
5 3
1 2 8 4 9
输出样例：
3
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
int n,m;
bool check(int mid)
{
int j=a[1],res=1;
for(int i=1;i<=n;i++)
{
if(a[i]-j>=mid)
{
j=a[i];
res++;
if(res>=m)return true;
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int l=1;
int r=a[n]-a[1];
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid; //如果此时两头牛之间的距离为mid,满足check（）,答案尽可能往大，故在mid的右半边
else r=mid-1;
}
cout<<r;
return 0;
}
（5）数列分段（与下一题同）
对于给定的一个长度为 N 的正整数数列 A，现要将其分成 M 段，并要求每段连续，且每段和的最大值最小。
例如，将数列 4,2,4,5,1 要分成 3 段：
若分为 (4,2),(4,5),(1)，各段的和分别为 6,9,1，和的最大值为 9；
若分为 (4),(2,4),(5,1)，各段的和分别为 4,6,6，和的最大值为 6；
并且无论如何分段，最大值不会小于 6。
所以可以得到要将数列 4,2,4,5,1 要分成 3 段，每段和的最大值最小为 6。
输入格式
第 1 行包含两个正整数 N,M；
第 2 行包含 N 个空格隔开的非负整数 Ai，含义如题目所述。
输出格式
仅包含一个正整数，即每段和最大值最小为多少。
数据范围
1≤N≤105,
1≤N≤M,
Ai 之和不超过 109。
输入样例：
5 3
4 2 4 5 1
输出样例：
6
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
int n,m;
bool check(int mid)
{
int tot=0;
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]+sum<=mid)sum+=a[i]; //前面能装，就装
else
{
sum=a[i]; //不能装了，另去一段去装，加加
tot++;
}
}
return tot<m;
}
int main()
{
cin>>n>>m;
int l=0;
int r=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
l=max(l,a[i]);
r+=a[i];
}
while(l<r)
{
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
(5)复制书稿
现在要把 m 本有顺序的书分给 k 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。
复制时间为抄写页数最多的人用去的时间。
输入格式
第一行两个整数 m，k。
第二行 m 个整数，第 i 个整数表示第 i 本书的页数。
输出格式
共 k 行，每行两个整数，第 i 行表示第 i 个人抄写的书的起始编号和终止编号。
k 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
数据范围
k≤m≤500
输入样例：
9 3
1 2 3 4 5 6 7 8 9
输出样例：
1 5
6 7
8 9
代码：
#include<iostream>
using namespace std;
const int N = 510;
int w[N], L[N], R[N]; //L 和 R 记录每一段的左右区间
int m, k;
bool check(int sum)
{
int s = 0, cnt = 1; //cnt表示被划分的段数
R[cnt] = m; //该段的右区间
//题目要求让前面的人尽可能少抄，那么就从序列后面往前面遍历，让后面的人尽可能多抄
for(int i=m; i; i--)
{
//
if(s + w[i] <= sum) s += w[i];
else
{
L[cnt] = i+1; //该段的左区间
cnt ++;
R[cnt] = i; //下一段的右区间
s = w[i]; //下一段重新开始累加
}
}
L[cnt] = 1;
return cnt <= k; //sum太大，导致被划分的段数少于等于k段
}
int main()
{
cin>>m>>k;
int l = 0, r = 1e9;
//读入m本书
for(int i=1; i<=m; i++)
{
cin>>w[i];
l = max(l, w[i]);
}
while(l < r)
{
int mid = l + r >>1;
if(check(mid)) r = mid;
else l = mid +1;
}
//此时l=r，check(r)以求出各段区间
check(r);
//cout<<r<<endl;
for(int i=k; i; i--) cout<<L[i]<<' '<<R[i]<<endl;
return 0;
}
总结：要将m本书顺序分成k个部分给k个人去抄，要使得抄书时间最短（大家同时开始抄，使得需要最长时间的那个人用时最短）。则我们只需要找到一个时间 time，能将m本书刚好划分为k个段给k个人抄写即可。那么如何找这个time呢？使用二分法找即可。
2.如何确定二分边界？
l = max(w[i])：因为一本书只能给一个人抄，因此 l 最小取所有书中的最大页数；
r = 1e9：题目未给定最大值，如果该值不满足条件，可以改成更大的值。
3.注意（贪心思路）
因为题目要求让前面的人尽可能少抄，因此求划分方案时应该从后往前枚举，即让后边的人尽可能多抄，就可以让前面的人少抄。
include[HTML_REMOVED]
作者：喜欢吃鱼
链接：https://www.acwing.com/solution/content/12336/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
美丽的数
如果一个数的所有数位上的数字都是 1，那么我们就称这个数是一个美丽的数。
并非所有数字都是美丽的，但是我们可以通过将一个十进制数转化为其他进制数，来使得该数变为一个美丽的数。
给定一个整数 N，你能通过将它改写为一个 B 进制数（B>1），从而使它的所有数位上的数字都变为 1 吗？
如果有多个答案满足要求，请输出最大化数位 1 的数量的答案。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据占一行，包含一个整数 N。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 x 是组别编号（从 1 开始），y 是满足条件的 B 的值。
数据范围
1≤T≤100,
3≤N≤1018
输入样例：
2
3
13
输出样例：
Case #1: 2
Case #2: 3
样例解释
样例#1，最佳方式是将 3 改写成二进制数 11。
样例#2，最佳方式是将 13 改写为三进制数 111，需要注意的是如果改写为十二进制数 11 也可满足要求，但是 111 的数位更多，所以选择改写为三进制。
难度：中等
时/空限制：1s / 64MB
总通过数：112
总尝试数：246
来源：Google Kickstart2016 Round E Problem B
算法标签
代码：
#include <iostream>
using namespace std;
typedef long long LL;
int check(LL n, LL b, int i)
{
LL res = 0;
for (int k = 0; k < i; k++)
{
if (res > (n - 1) / b) return 1; //使用除法，防止数据溢出, res * b + 1会溢出
res = res * b + 1;
}
if (res == n) return 0;
return -1;
}
int main()
{
int T;
cin >> T;
//整数n能不能用某一个进制b表示成连续i个1的形式
//从大到小枚举i
//二分出进制b，满足进制数大于b的进制表示下，n小于连续i个1，小于b的进制n大于连续i个1表示的数
//最终答案就是n等于连续i个1表示的数
for (int t = 1; t <= T; t++)
{
LL n;
cin >> n;
for (int i = 63; i > 0; i--) //二分枚举
{
LL l = 2, r = n;
while (l < r)
{
LL mid = (l + r) / 2;
if (check(n, mid, i) >= 0) r = mid;
else l = mid + 1;
}
if (check(n, l, i) == 0) //整数n可以在l进制下表示i位1.
{
printf("Case #%d: %lld\n", t, l);
break;
}
}
}
return 0;
}
奶牛棒球
农夫约翰的 N 头奶牛排成一排，每头奶牛都位于数轴中的不同位置上。
它们正在练习投掷棒球。
农夫约翰观看时，观察到一组三头牛 (X,Y,Z) 完成了两次成功的投掷。
牛 X 把球扔给她右边的牛 Y，然后牛 Y 把球扔给她右边的牛 Z。
约翰指出，第二次投掷的距离不少于第一次投掷的距离，也不超过第一次投掷的距离的两倍。
请计算共有多少组牛 (X,Y,Z) 可能是约翰所看到的。
输入格式
第一行包含整数 N。
接下来 N 行，每行描述一头牛的位置。
输出格式
输出奶牛三元组 (X,Y,Z) 的数量。
(X,Y,Z) 需满足，Y 在 X 的右边，Z 在 Y 的右边，并且从 Y 到 Z 的距离在 [XY,2XY] 之间，其中 XY 表示从 X 到 Y 的距离。
数据范围
3≤N≤1000,
奶牛所在的位置坐标范围 [0,108]。
输入样例：
5
3
1
10
7
4
输出样例：
4
样例解释
四个可能的奶牛三元组为：1−3−7,1−4−7,4−7−10,1−4−10。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i<=n; i++) scanf("%d", &a[i]);
sort(a+1, a+n+1);//对二分数组排序
int num = 0;//记录最终三元组的个数
for(int i = 1; i<=n; i++){//枚举前两号牛的位置
for(int j = i+1; j<=n; j++){
int ans = a[j] - a[i];//ans为前两号牛之间的距离
int tot = lower_bound(a+1, a+n+1, ans+a[j]) - a;//找到第一个距离大于等于ans的牛的位置
int cnt = upper_bound(a+1, a+n+1, 2*ans+a[j]) - a;//找到第一个距离大于2*ans的牛的位置
num+=cnt - tot;//之间的所有牛都可以组成合法三元组
}
}
cout<<num<<endl;
return 0;
}
工资计算
小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。
假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为 S 元，则他应交的个人所得税按如下公式计算：
个人所得税起征点为 3500 元，若 S 不超过 3500，则不交税，3500 元以上的部分才计算个人所得税，令 A=S−3500 元；
A 中不超过 1500 元的部分，税率 3%；
A 中超过 1500 元未超过 4500 元的部分，税率 10%；
A 中超过 4500 元未超过 9000 元的部分，税率 20%；
A 中超过 9000 元未超过 35000 元的部分，税率 25%；
A 中超过 35000 元未超过 55000 元的部分，税率 30%；
A 中超过 55000 元未超过 80000 元的部分，税率 35%；
A 中超过 80000 元的部分，税率 45%；
例如，如果小明的税前工资为 10000 元，则 A=10000−3500=6500 元，其中不超过 1500 元部分应缴税 1500×3%=45 元，超过 1500 元不超过 4500 元部分应缴税 (4500−1500)×10%=300 元，超过 4500 元部分应缴税 (6500−4500)×20%=400 元。
总共缴税 745 元，税后所得为 9255 元。
已知小明这个月税后所得为 T 元，请问他的税前工资 S 是多少元。
输入格式
输入的第一行包含一个整数 T，表示小明的税后所得。
所有评测数据保证小明的税前工资为一个整百的数。
输出格式
输出一个整数 S，表示小明的税前工资。
数据范围
对于所有评测用例，1≤T≤100000。
输入样例：
9255
输出样例：
10000
难度：简单
时/空限制：1s / 256MB
总通过数：259
总尝试数：542
来源：第九次CCF计算机软件能力认证
算法标签
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int check(int mid)
{
int a[] = {0, 1500, 4500, 9000, 35000, 55000, 80000, 1000000};
double r[] = {0, 0.03, 0.1, 0.2, 0.25, 0.3, 0.35, 0.45};
if(mid<=3500)return mid;
int ans = mid-3500;
double sum=0;
for(int i=1;i<=7;i++)
{
if(ans-a[i]>=0)
{
sum+=(a[i]-a[i-1])*r[i];
}
else
{
sum+=(ans-a[i-1])*r[i];
break;
}
}
return mid-sum;
}
int main()
{
int t;
cin>>t;
int l=t;
int r=2*t;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)>=t)r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
第k个数
给定一个 n×m 的方格矩阵，每个方格内都有一个整数元素。
其中第 i 行第 j 列的方格中的元素为 i×j（行和列都从 1 开始编号）。
现在，需要你将这 n×m 个整数按照非严格单调递增的顺序一一写出。
请问，你写出的第 k 个整数是多少。
输入格式
一行，三个整数 n,m,k。
输出格式
一行，输出你写出的第 k 个整数。
数据范围
前 6 个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n,m≤5×105，1≤k≤n×m。
输入样例1：
2 2 2
输出样例1：
2
输入样例2：
2 3 4
输出样例2：
3
输入样例3：
1 10 5
输出样例3：
5
代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,m,k;
bool check(LL mid)
{
LL res=0;
for(int i=1;i<=n;i++)
{
res+=min(mid/i,m); //每一行中i*j<=mid 的数
}
return res>=k;
}
int main()
{
cin>>n>>m>>k;
LL l=0;
LL r=n*m;
while(l<r)
{
LL mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<r;
return 0;
}
最大中位数
给定一个由 n 个整数组成的数组 a，其中 n 为奇数。
你可以对其进行以下操作：
选择数组中的一个元素（例如 ai），将其增加 1（即，将其替换为 ai+1）。
你最多可以进行 k 次操作，并希望该数组的中位数能够尽可能大。
奇数长度的数组的中位数是数组以非降序排序后的中间元素。
例如，数组 [1,5,2,3,5] 的中位数为 3。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数 a1,a2,…,an。
输出格式。
输出一个整数，表示通过操作可能得到的最大中位数。
数据范围
对于 30% 的数据，1≤n≤5。
对于 100% 的数据，1≤n≤2×105，1≤k≤109，1≤ai≤109。
输入样例1：
3 2
1 3 5
输出样例1：
5
输入样例2：
5 5
1 2 1 1 1
输出样例2：
3
输入样例3：
7 7
4 1 2 4 3 4 4
输出样例3：
5
代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int w[N];
int n,k;
bool check(LL mid)
{
LL res=0;
for(int i=n/2;i<n;i++)
{
if(w[i]<mid) //中位数的右边如果比mid小，操作如果小于k次则符合
{
res+=mid-w[i];
}
}
return res<=k;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)cin>>w[i];
sort(w,w+n);
LL l=0;
LL r=2e9; //如果只有一个数1e9
while(l<r)
{
LL mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
*训练*
达尔星有 n 个强大的下级战士，编号 1∼n。
其中第 i 名战士的战斗力为 ri。
战士 a 可以成为战士 b 的战斗导师，当且仅当 ra>rb 且两人之间不存在矛盾。
给定每个战士的战斗力值以及战士之间存在的 k 对矛盾关系。
请你计算，每个战士可以成为多少战士的战斗导师。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数 r1,r2,…,rn。
接下来 k 行，每行包含两个整数 x,y，表示战士 x 和战士 y 之间存在矛盾。同一对矛盾关系不会在输入中重复给出，即出现了 x,y 以后，后面就不会再次出现 x,y 或 y,x。
输出格式
共一行，n 个整数，表示每个战士可以作为战斗导师的战士数量。
数据范围
前三个测试点满足，2≤n≤10，0≤k≤10。
所有测试点满足，2≤n≤2×105，0≤k≤min(2×105,n(n−1)2)，1≤ri≤109，1≤x,y≤n，x≠y。
输入样例：
4 2
10 4 10 15
1 2
4 3
输出样例：
0 0 1 2
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2e5+10;
int a[N];
int b[N];
int ans[N];
int k;
int n;
int x;
int y;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]); //原数组
b[i]=a[i]; //用b数组排序二分查找
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
int l=0;
int r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(b[mid]<a[i])l=mid; ///a[i]找到在数组中比自己还小的树有几个，如果mid符合，看能否多找到几个，
else r=mid-1; //故在mid右半边
}
ans[i]=l;
}
for(int i=1;i<=k;i++)
{
cin>>x>>y;
if(a[x]>a[y]) ans[x]--;
if(a[x]<a[y]) ans[y]--;
}
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
}
