二分
1.一维常见题
789. 数的范围 - AcWing题库
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
输出样例：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] s = in.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int q = Integer.parseInt(s[1]);
int[] nums = new int[n + 2];
s = in.readLine().split(" ");
for (int i = 1; i <= n; i++) {
nums[i] = Integer.parseInt(s[i - 1]);
}
nums[n + 1] = 20000;
for (int i = 0; i < q; i++) {
int x = Integer.parseInt(in.readLine());
fun(x, nums);
}
}
private static void fun(int x, int[] nums) {
int l = findLow(x, nums) - 1;
int r = findBig(x, nums) - 1;
if (l < r) {
System.out.println("-1 -1");
} else {
System.out.println(r + " " + l);
}
}
private static int findBig(int x, int[] nums) {
int l = 0;
int r = nums.length;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
private static int findLow(int x, int[] nums) {
int l = 0;
int r = nums.length;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
}
|
2.练习-二分答案
1460. 我在哪？ - AcWing题库
农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共 N个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K 的值，使得他查看任意连续 K个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4=4，因为如果他查看任意连续 44 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z之内。
输出格式
输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 K 值。
数据范围
1≤N≤100
输入样例：
输出样例：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String s = in.readLine();
int l = 0;
int r = s.length();
while (l < r) {
int mid = l + r >> 1;
if (check(mid, s)) {
r = mid;
} else {
l = mid + 1;
}
}
System.out.println(l);
}
private static boolean check(int mid, String s) {
HashSet<String> set = new HashSet<>();
for (int i = 0; i <= s.length() - mid; i++) {
String substring = s.substring(i, i + mid);
if (set.contains(substring)) {
return false;
}
set.add(substring);
}
return true;
}
}
|
3.练习
1221. 四平方和 - AcWing题库
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 44 个正整数的平方和。
如果把 00 包括进去，就正好可以表示为 44 个数的平方和。
比如：
5=02+02+12+225=02+02+12+22  
7=12+12+12+227=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 44 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗106
输入样例：
输出样例：
代码 -二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine();
ArrayList<int[]> arrayList = new ArrayList<>();
int n = Integer.parseInt(s);
for (int i = 0; i * i <= n; i++) {
for (int j = i; j * j + i * i <= n; j++) {
arrayList.add(new int[]{i * i + j * j, i, j});
}
}
Collections.sort(arrayList, (o1, o2) -> {
if (o1[0]!= o2[0]) {
return o1[0] - o2[0];
} else if (o1[1]!= o2[1]) {
return o1[1] - o2[1];
} else {
return o1[2] - o2[2];
}
});
for (int i = 0; i * i <= n; i++) {
for (int j = i; j * j + i * i <= n; j++) {
int t = n - i * i - j * j;
int l = 0;
int r = arrayList.size() - 1;
while (l < r) {
int mid = l + r >>1;
if (arrayList.get(mid)[0] < t) {
l = mid + 1;
} else {
r = mid;
}
}
if (arrayList.get(l)[0] == t) {
System.out.println(i + " " + j + " " + arrayList.get(l)[1] + " " + arrayList.get(l)[2]);
return;
}
}
}
}
}
|
代码 -暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine();
int n = Integer.parseInt(s);
for (int i = 0; i * i * 4 <= n; i++) {
for (int j = i; i * i + j * j * 3 <= n; j++) {
for (int k = j; i * i + j * j + k * k * 2 <= n; k++) {
int t = n - i * i - j * j - k * k;
int tt = (int) Math.sqrt(t);
if (tt * tt == t) {
System.out.println(i + " " + j + " " + k + " " + tt);
return;
}
}
}
}
}
}
|
4.练习
1227. 分巧克力 - AcWing题库
儿童节那天有 K位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×11×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105
1≤Hi,Wi≤105
输入样例：
输出样例：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] s = in.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int k = Integer.parseInt(s[1]);
int[][] nums = new int[n][2];
for (int i = 0; i < n; i++) {
s = in.readLine().split(" ");
nums[i][0] = Integer.parseInt(s[0]);
nums[i][1] = Integer.parseInt(s[1]);
}
int i = 1;
int j = 100000;
while (i < j) {
int mid = i + j + 1 >> 1;
if (check(mid, nums) >= k) {
i = mid;
} else {
j = mid - 1;
}
}
System.out.println(i);
}
private static int check(int mid, int[][] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
res = res + (nums[i][0] / mid) * (nums[i][1] / mid);
}
return res;
}
}
|
