[蓝桥杯]真题讲解：抓娃娃（思维+二分）

一、视频讲解

[蓝桥杯]真题讲解：抓娃娃（思维+二分））

二、正解代码

1、C++

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5 + 10;
int n, m;

int main()
{
	cin >> n >> m;
	vector<pii>a(n);
	vector<double>b(m);

	for(int i = 0; i < n; i ++) {
		int L, R; cin >> L >> R;
		double mid = (L + R) / 2.0;
		b[i] = mid;
	}
	for(int i = 0; i < m; i ++) {
		cin >> a[i].x >> a[i].y;
	}
	sort(b.begin(), b.end());

	auto check1 = [&](int mid, int i) {
		return b[mid] >= a[i].x;
	};

	auto check2 = [&](int mid, int i) {
		return b[mid] <= a[i].y;
	};

	for(int i = 0; i < m; i ++) {
		int L = a[i].x, R = a[i].y;
		int l1 = 0, r1 = n - 1;
		while(l1 < r1) {
			int mid = l1 + r1 >> 1;
			if(check1(mid, i))
				r1 = mid;
			else
				l1 = mid + 1;
		}
		int l2 = 0, r2 = n - 1;
		while(l2 < r2) {
			int mid = l2 + r2 + 1 >> 1;
			if(check2(mid, i))
				l2 = mid;
			else
				r2 = mid - 1;
		}
		if(b[l1] >= L && b[l2] <= R) {
			cout << l2 - l1 + 1 << endl;
		}else{
      		cout << 0 << endl;
    	}
	}
	return 0;
}

2、python3

n, m = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(n)]
b = []
for x, y in tmp:
    b.append ((x + y) / 2.0)

a = [list(map(int, input().split())) for _ in range(m)]

b.sort()

def check1(mid: int, i: int)->bool:
    return b[mid] >= a[i][0]

def check2(mid: int, i: int)->bool:
    return b[mid] <= a[i][1]

for i in range(m):
    L, R = a[i]
    l1, r1 = 0, n - 1
    while l1 < r1:
        mid = (l1 + r1) // 2
        if check1(mid, i):
            r1 = mid
        else:
            l1 = mid + 1
    l2, r2 = 0, n - 1
    while l2 < r2:
        mid = (l2 + r2 + 1) // 2
        if check2(mid, i):
            l2 = mid
        else:
            r2 = mid - 1
    if b[l1] >= L and b[l2] <= R:
        print(l2 - l1 + 1)
    else:
        print(0)

3、Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int n, m;
    public static double[] b;
    public static int[][] a;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        b = new double[n];
        a = new int[n][2];
        for(int i = 0; i < n; i ++) {
            int L = sc.nextInt();
            int R = sc.nextInt();
            double mid = (L + R) / 2.0;
            b[i] = mid;
        }
        for(int i = 0; i < m; i ++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        Arrays.sort(b);
        for(int i = 0; i < m; i ++) {
            int L = a[i][0], R = a[i][1];
            int l1 = 0, r1 = n - 1;
            while(l1 < r1){
                int mid = l1 + r1 >> 1;
                if(check1(mid, i)) {
                    r1 = mid;
                }else{
                    l1 = mid + 1;
                }
            }
            int l2 = 0, r2 = n - 1;
            while(l2 < r2) {
                int mid = l2 + r2 + 1 >> 1;
                if(check2(mid, i)){
                    l2 = mid;
                }else{
                    r2 = mid - 1;
                }
            }
            if(b[l1] >= L && b[l2] <= R) {
                System.out.println(l2 - l1 + 1);
            }else{
                System.out.println(0);
            }
        }
    }
    private static boolean check1(int mid, int i) {
        return b[mid] >= a[i][0];
    }
    private static boolean check2(int mid, int i){
        return b[mid] <= a[i][1];
    }
}