二分答案

和二分查找中查找某个元素第一次出现的位置和最后一次出现的位置相似，二分答案是求最小化答案xmin 或最大化答案 xmax​，所以写法上和二分查找一脉相承。

选择一种二分查找的写法，加以扩展即可。

//最小化答案
bool check(int x) {
  ...           // 计算 y
  return y >= C; //x大y大
  return y <= C; //x小y大
}

int find(int x) {
    int L = 下界-1, R = 上界+1;
    while (L + 1 < R) {
        int mid = (L + R) / 2; 
        if (check(mid)) { // 将二分查找的 比较判断改为根据check函数返回值判断
            R = mid;
        } else {
            L = mid;
        }
    }
    return R;
}

//最大化答案
bool check(int x) {
  ...           // 计算 y
  return y <= C; //x小y小
  return y >= C; //x小y大
}

int find(int x) {
    int L = 下界-1, R = 上界+1;
    while (L + 1 < R) {
        int mid = (L + R) / 2; // 若用位运算写作 L + R >> 1;
        if (check(mid)) {
            L = mid;
        } else {
            R = mid;
        }
    }
    return L;
}

历年真题

2021CSP普及组第20道题完善程序题

（矩形计数）平面上有nn个关键点，求有多少个四条边都和xx轴或者yy轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。 试补全枚举算法。

1 	#include <stdio.h>
2 
3 	struct point {
4 		int x, y, id;
5 	};
6 
7 	int equals(struct point a, struct point b){
8 		return a.x == b.x && a.y == b.y;
9 	}
10
11	int cmp(struct point a, struct point b){
12		return  ①; 
13	}
14
15	void sort(struct point A[], int n){
16		for (int i = 0; i < n; i++)
17			for (int j = 1; j < n; j++)
18				if (cmp(A[j], A[j - 1])){
19					struct point t = A[j];
20					A[j] = A[j - 1];
21					A[j - 1] = t;
22				}
23	}
24
25	int unique(struct point A[], int n){
26		int t = 0;
27		for (int i = 0; i < n; i++)
28			if (②)
29				A[t++] = A[i];
30		return t;
31	}
32
33	int binary_search(struct point A[], int n, int x, int y){
34		struct point p;
35		p.x = x;
36		p.y = y;
37		p.id = n;
38		int a = 0, b = n - 1;
39		while(a < b){
40			int mid = ③;
41			if (④)
42				a = mid + 1;
43			else 
44				b = mid; 
45		}
46			return equals(A[a], p);
47	}
48
49	#define MAXN 1000
50	struct point A[MAXN];
51
52	int main(){
53		int n;
54		scanf("%d", &n);
55		for (int i = 0; i < n; i++){
56			scanf("%d %d", &A[i].x, &A[i].y);
57			A[i].id = i;
58		}
59		sort(A, n);
60		n = unique(A, n);
61		int ans = 0;
62		for (int i = 0; i < n; i++)
63			for (int j = 0; j < n; j++)
64			if ( ⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)){
65							ans++;
66			}
67		printf("%d\n", ans); 
68		return 0;
69	}

①处应填（） ②处应填（） ③处应填（） ④处应填（） ⑤处应填（）

A.a.x != b.x ? a.x < b.x : a.id < b.id B.a.x != b.x ? a.x < b.x : a.y < b.y C.equals(a,b) ? a.id < b.id : a.x < b.x D.equals(a,b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

A.i == 0 || cmp(A[i], A[i - 1]) B.t == 0 || equals(A[i], A[t - 1]) C.i == 0 || !cmp(A[i], A[i - 1]) D.t == 0 || !equals(A[i], A[t - 1])

A.b - (b - a) / 2 + 1 B.(a + b + 1) >> 1 C.(a + b) >> 1 D.a + (b - a + 1) / 2

A.!cmp(A[mid], p) B.cmp(A[mid], p) C.cmp(p, A[mid]) D.!cmp(p, A[mid])

A.A[i].x == A[j].x B.A[i].id < A[j].id C.A[i].x == A[j].x && A[i].id < A[j].id D.A[i].x < A[j].x && A[i].y < A[j].y

阅读程序题

01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09     int l = 0, r = n;
10     while (l <= r) {
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17
18 double solve2(double x)
19 {
20     if (x == 0) return x;
21     for (int i = 0; i < k; i++)
22         x = (x + n / x) / 2;
23     return x;
24 }
25
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数，完成下面的判断题和单选题：

判断题

28 ) 该算法最准确的时间复杂度分析结果为𝑂(log 𝑛 + 𝑘)。（ ）

29 ) 当输入为“9801 1”时，输出的第一个数为“99”。（ ）

30 ) 对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）

31 ) 该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将mid 强制转换为 64 位整数再计算。（ ）

单选题

32 ) 当输入为“2 1”时，输出的第一个数最接近（ ）。

A. 1

B. 1.414

C. 1.5

D. 2

33 )当输入为“3 10”时，输出的第一个数最接近（ ）。

A. 1.7

B. 1.732

C. 1.75

D. 2

34 ) 当输入为“256 11”时，输出的第一个数（ ）。

A. 等于 16

B. 接近但小于 16

C. 接近但大于 16

D. 前三种情况都有可能

(寻找被移除的元素)问题:原有长度为 n+1，公差为1的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。 33 ①处应填（ ）

A. 1 B.nums[0] C.right D.left

34 ②处应填（ ）

A. left=mid+1 B.right=mid-1 C.right=mid D.left=mid

35 ③处应填（ ）

A.left=mid+1 B.right=mid-1 C.right=mid D.left=mid

36 ④处应填（ ）

A.left+nums[0] B.right+nums[0] C.mid+nums[0] D.right+1

37 ⑤处应填（ ）

A.nums[0]+n B.nums[0]+n-1 C.nums[0]+n+1 D.nums[n-1]