import java.util.*;
/**
* 工厂老张
* 时间限制: 3000MS
* 内存限制: 589824KB
* 题目描述:
* 老张是一个工厂里的工人。他每天的工作就是坐在工厂流水线旁检查产品的质量。一天,流水线运来了一批产品,一共有n个,每个产品的质量用一个正整数ai表示。评价这些产品的好坏有一个“一致程度”的指标,“一致程度”指的是一批产品中质量相同的产品的最大个数。例如:如果一批产品的质量是“3 2 1 2 2 3”,质量为“1”的产品有1个,质量为“2”的产品有3个,质量为“3”的产品有2个,那么这批产品的“一致程度”就是3。现在老张需要从这些产品中选出一段连续的序列,使得该序列的“一致程度”与总的n个产品的“一致程度”相同,同时保证选出的序列长度最短。你能写一个程序实现这个操作吗?
*
*
*
* 输入描述
* 第一行有一个整数n,表示产品的数量。
*
* 第二行有n个空格隔开的整数,每个整数表示一个产品的质量。
*
* 输入保证只有一个答案符合要求。
*
* 1≤n≤100000。
*
* 1≤ai≤10000。
*
* 输出描述
* 输出两个整数,空格隔开,第一个整数表示所选序列的左端点的位置,第二个整数表示所选序列的右端点的位置。两个整数中间用一个空格隔开。
*
*
* 样例输入
* 6
* 3 2 1 2 2 3
* 样例输出
* 2 5
*
* 提示
* 样例解释
*
* 原数列的”一致程度”为3,所选序列从2到5,也就是“2 1 2 2”,其“一致程度”也为3,并且长度最短。
*
*
*/
public class Test1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] num = new int[n];
for(int i = 0;i<n;i++){
num[i] = sc.nextInt();
}
Map<Integer,Integer> map = new HashMap<>();
int count = 0;
for(int i = 0;i<n;i++){
map.put(num[i],map.getOrDefault(num[i],0)+1);
if(map.get(num[i])>count){
count = map.get(num[i]);
}
}
int minLeft = 0;
int minRight = Integer.MAX_VALUE;
Set<Integer> set = new HashSet<>();
for(int i = 0;i<n;i++){
if(!set.contains(num[i])&&map.get(num[i])==count){
int right = n-1;
while(num[right]!=num[i]){
right--;
}
if(right-i<minRight-minLeft){
minLeft = i;
minRight = right;
}
set.add(num[i]);
}
}
System.out.println((minLeft+1)+" "+(minRight+1));
}
}
import java.util.Arrays;
import java.util.Scanner;
/**
* 稳固积木
* 时间限制: 3000MS
* 内存限制: 589824KB
* 题目描述:
* 小明手中有n块积木,并且小明知道每块积木的重量。现在小明希望将这些积木堆起来,要求是任意一块积木如果想堆在另一块积木上面,那么上面积木的重量减去下面积木的重量不能超过x(每堆中最下面的积木没有重量要求)。现在小明有一个机会,除了这n块积木,还可以获得k块任意重量的积木。小明希望将积木堆在一起,同时希望积木堆的数量越少越好,你能帮他找到最好的方案么?
*
*
*
* 输入描述
* 第一行三个整数n,k,x,1<=n<=200000,0<=x,k<=1000000000
*
* 第二行n个整数,表示积木的重量,任意整数范围都在[1,1000000000]
*
* 数字间均有空格隔开
*
* 输出描述
* 一个整数,表示可以堆出的最少积木堆的数量。
*
*
* 样例输入
* 8 2 3
* 1 1 5 8 12 13 20 22
* 样例输出
* 2
*
* 提示
* 样例2:
*
* 输入:
*
* 13 0 37
*
* 20 20 80 70 70 70 420 5 1 5 1 60 90
*
* 输出:
*
* 3
*
* 解释:
*
* 三堆分别是
*
* 1 1 5 5 20 20;
*
* 60 70 70 70 80 90;
*
* 420
*
*
*/
public class Test2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int x = sc.nextInt();
int[] num = new int[n];
for(int i = 0;i<n;i++){
num[i] = sc.nextInt();
}
Arrays.sort(num);
int heapCount = 1;
for(int i = 1;i<n;i++){
if(num[i]-num[i-1]>x){
if(k>0&&num[i]-num[i-1]<=2*x){
k--;
}else{
heapCount++;
}
}
}
System.out.println(heapCount);
}
}