小贪心

用户名：uq_90082943905

访问量：2776

签　名：

等　　级
排　　名	5387
经　　验	1547
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-8皇后·改 -题解(Java代码)
浏览：401

信息学奥赛一本通T1320-均分纸牌-题解(Java代码)
浏览：259

信息学奥赛一本通T1324-整数区间-题解(Java代码)
浏览：614

你可能喜欢

信息学奥赛一本通T1324-整数区间-题解(Java代码)

　　作者: 小贪心　　　　发表时间：2020-02-27 11:55:57 浏览：614　|　评论：0　

原题链接：信息学奥赛一本通T1324-整数区间

## 整数区间

时间限制: 1Sec 内存限制: 128MB

**题目描述**
请编程完成以下任务：

1.从文件中读取闭区间的个数及它们的描述；

2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。

**输入**
首行包括区间的数目n,1≤n≤10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0≤a≤b≤10000,它们是某一个区间的开始值和结束值。
**输出**
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。
**样例输入**
4
3 6
2 4
0 2
4 7
**样例输出**
2

## 思路
模型为**给n个闭区间，在数轴上选尽量少的点，使每个区间内至少有一个点**

首先**多关键词排序**：数据按右区间升序排序。排序优先级：右区间>左区间，也就是当右区间相同时，升序比较左区间。
其次**循环标记**：每次标记区间右端点x，并右移当前区间指针，直到当前区间不包含x，再重复上述步骤。

```java
import java.util.Scanner;

public class Main {
	static int[] a=new int[10001];
	static int[] b=new int[10001];
	static int n=0;
	public static void main(String[] args){
		data();   //数据初始化
		qsort(0,n-1);  //多关键词排序
		solve();  //循环标记
	}
	static void data(){
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		for(int j=0;j<n;j++){
			a[j]=sc.nextInt();
			b[j]=sc.nextInt();
		}
	}
	
	static void qsort(int x,int y){
		int i=x , j=y ,mid1=b[(x+y)/2] , mid2=a[(x+y)/2], t=0;
		while(i<=j){
			while((b[i]<mid1)|| ((b[i]==mid1)&& (a[i]<mid2))) i++;  //比较条件
			while((b[j]>mid1)|| ((b[j]==mid1)&& (a[j]>mid2))) j--;  //比较条件
			if(i<=j){
				t=b[i]; b[i]=b[j]; b[j]=t;
				t=a[i]; a[i]=a[j]; a[j]=t;
				i++;j--;
			}
		}
		if(x<j) qsort(x,j);
		if(i<y) qsort(i,y);
			
	}
	static void solve(){
		int sum=0;
		for(int i=0,x=-1;i<n;i++){
			if(x>=a[i]) continue;   //如果当前区间包含标记点 则跳过
			sum++; 					
			x=b[i];					//更新标记点
		}
		System.out.print(sum);
	}
}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小贪心

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

The 3n + 1 problem （C语言代码）

C二级辅导-同因查找（C语言代码）

【绝对值排序】（C++代码）

信息学奥赛一本通T1324-整数区间-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

关于float，double变量的几点说明

罗列完美数（C语言代码）

川哥的吩咐（C语言代码）

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

10月月赛题解

小贪心

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

The 3n + 1 problem （C语言代码）

C二级辅导-同因查找 （C语言代码）

【绝对值排序】 （C++代码）

信息学奥赛一本通T1324-整数区间-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

关于float，double变量的几点说明

罗列完美数 （C语言代码）

川哥的吩咐 （C语言代码）

数组输出 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

10月月赛题解

C二级辅导-同因查找（C语言代码）

【绝对值排序】（C++代码）

　　评论区

罗列完美数（C语言代码）

川哥的吩咐（C语言代码）

数组输出（C语言代码）