👨🏫 题目地址
输入
3
2
1 6
3 -7 7 10
4
9 -5 -9 2 8 5 4 3 3 8
2 10 8
1 -7
3 1 6 10
1
1 9
输出
1
15
0
使用快读,避免使用 Arrays.fill() 按需初始化 避免卡常
🍑 思路文章来源:https://www.toymoban.com/news/detail-612667.html
文章来源地址https://www.toymoban.com/news/detail-612667.html
🍺 AC code
import java.io.*;
import java.util.*;
public class Main
{
// static Scanner sc = new Scanner(System.in);
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = 1000010;
static int[] buc = new int[N];
static List<Pair> list = new ArrayList<>();
static class Pair
{
int x, y;// x表示值,y表示编号
public Pair(int x, int y)
{
super();
this.x = x;
this.y = y;
}
}
static void solve() throws IOException
{
// int k = sc.nextInt();
int k = Integer.parseInt(in.readLine());
for (int i = 1; i <= k; i++)
{
// int size = sc.nextInt();
String[] ss = in.readLine().split(" ");
int size = Integer.parseInt(ss[0]);
for (int j = 1; j <= size; j++)
{
// int x = sc.nextInt();
int x = Integer.parseInt(ss[j]);
list.add(new Pair(x, i));
}
}
Collections.sort(list, (o1, o2) -> o1.x - o2.x);//根据x的值排升序
int ans = (int) 2e9;//记录最小值的答案
int cnt = 0;//cnt记录区间有多少个 集合 的元素了,当 cnt == k 时,满足题目条件
for (int i = 0, j = 0; i < list.size(); i++)//i 表示区间右指针
{
int num = list.get(i).y;// num表示的是当前元素的编号(在第几个集合)
++buc[num];//记录当前集合有多少个元素在 [j,i] 的区间内
if (buc[num] == 1)
cnt += 1;//注意:cnt只加不减,说明只要第一次达到条件之后,后续的所有操作都不会导致无法达到条件
// j<i保证区间长度不为0,buc[list.get(j).y] > 1 保证当前区间必须符合题目条件(
//即每个集合都至少有一个元素在当前区间)(保证 cnt 一直等于 k)
for (; j < i && buc[list.get(j).y] > 1; j++)
buc[list.get(j).y]--;//删除区间左端点【可以删除】的 多余元素
if (cnt == k)
ans = Math.min(ans, list.get(i).x - list.get(j).x);
}
// System.out.println(ans);
out.write(ans + "\n");
//全部变量初始化
list.clear();
// Arrays.fill(buc, 0);
for (int i = 0; i <= k; i++)
buc[i] = 0;
}
public static void main(String[] args) throws IOException
{
// int T = sc.nextInt();
int T = Integer.parseInt(in.readLine());
while (T-- > 0)
{
solve();
}
out.flush();
}
}
到了这里,关于杭电oj Simple Set Problem 双指针 尺取法 满注释版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!