[蓝桥杯 2024 国 Java B] 美丽区间

问题描述

美丽区间是这样的一组区间：[L1,R1]、[L2,R2]、[L3,R3].. 构造美丽区间需要满足以下条件：

1. L1=1
2. Li≤Ri
3. Ri−Li≥K
4. 对于任意的 i>1，有 Li=Ri−1  +1
5. gcd(Li,Ri)=1，其中 gcd指两个数的最大公约数
6. 在满足上述条件的情况下，Li、Ri​ 之间的差尽可能的小。

输入格式

第一行输入一个整数 K。 第二行输入一个整数 T，表示有 T 组测试用例。 接下来 T 行，每行输入一个整数 n。

输出格式

对每个输入的整数 n，输出一行，包含一个整数，表示 n 属于第几个美丽区间。

样例输入

10
3
123
33
10

样例输出

11
3
1

样例说明

第 1 个美丽区间为：[1,11]。

第 2 个美丽区间为：[12,23]。

第 3 个美丽区间为：[24,35]。

⋯⋯

第 11 个美丽区间为：[120,131]。

评测用例规模与约定

对于 60% 的评测用例：1≤T≤10^3，1≤K≤10^6，1≤n≤10^6。

对于 100% 的评测用例：1≤T≤10^6，1≤K≤10^6，1≤n≤10^6。

解题思路

要找出输入的整数在第几个区间，因为我们可以先根据题目要求把所有的美丽区间找到，并存储好美丽区间的左边界以及该区间属于第几个区间。

为了方便我们后续进行查找，我们可以用TreeMap存储这些数据，key存储左边界，value存储第几区间。

因为 TreeMap内部已经封装了基于红黑树的高效查找逻辑，并提供了一系列方法直接支持范围查询、上下界查找等操作。可以直接使用floorEntry()方法查找<=n的最大键值对，再用getValue()取值就能得到属于第几个区间。

代码

import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		//key存储区间左边界，value存储属于第几个区间
		TreeMap<Integer, Integer> map=new TreeMap<>();
        int l=1;
        int cnt=1;
		map.put(l,cnt);//存储第一个区间
		l=k+2;//从第二个区间开始
		cnt=2;
		while(l<=1000000) {
			int r=l+k;
			while(gcd(l,r)!=1) {
				r++;
			}
			map.put(l, cnt);
			l=r+1;
			cnt++;
		}
		
		int t=sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
			//查找<=n的最大键值对，再取值
			int res=map.floorEntry(n).getValue();
			System.out.println(res);
		}
		sc.close();
	}
	
	private static int gcd(int a,int b) {
		return b==0?a:gcd(b,a%b);
	}

}