杭电oj Simple Set Problem 双指针 尺取法 满注释版

这篇具有很好参考价值的文章主要介绍了杭电oj Simple Set Problem 双指针 尺取法 满注释版。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

👨‍🏫 题目地址

杭电oj Simple Set Problem 双指针 尺取法 满注释版,算法题解,android
输入

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() 按需初始化 避免卡常

🍑 思路

杭电oj Simple Set Problem 双指针 尺取法 满注释版,算法题解,android文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1063 Set Similarity(详细注释+35代码+set的妙用)

    分数 25 全屏浏览题目 作者 CHEN, Yue 单位 浙江大学 Given two sets of integers, the similarity of the sets is defined to be Nc​/Nt​×100%, where Nc​ is the number of distinct common numbers shared by the two sets, and Nt​ is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any give

    2024年02月05日
    浏览(35)
  • C++ 双指针思路OJ题

    目录 一、283. 移动零 二、1089. 复写零 三、202. 快乐数 四、11. 盛最多水的容器 五、611.有效三角形的个数 六、LCR 179. 查找总价格为目标值的两个商品 七、15. 三数之和 八、18. 四数之和 思路:变量cur从零开始负责遍历数组,dest起始在-1位置,负责找到值为0的元素。遍历数组,

    2024年01月23日
    浏览(37)
  • 【C++】map/multimap/set/multiset的经典oj例题 [ 盘点&全面解析 ] (28)

    前言 大家好吖,欢迎来到 YY 滴C++系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《初学者易

    2024年02月04日
    浏览(45)
  • 【链表OJ 11】复制带随机指针的链表

    前言:  💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 leetcode138. 复制带随机指针的链表 1. 问题描述 2.代码思路: 2.1拷贝节点插入到原节点的后面 2.2控制拷贝节点的random     2.3拷贝节点解下来尾插组成拷

    2024年02月09日
    浏览(51)
  • 【高阶数据结构】map和set的介绍和使用 {关联式容器;键值对;map和set;multimap和multiset;OJ练习}

    关联式容器和序列式容器是C++ STL中的两种不同类型的容器。 关联式容器是基于键值对的容器 ,其中每个元素都有一个唯一的键值,可以通过键值来访问元素。关联式容器包括set、multiset、map和multimap。 序列式容器是基于元素序列的容器 ,其中元素按照一定的顺序排列,可以

    2024年02月11日
    浏览(41)
  • 【C++】unordered_map和unordered_set的使用 及 OJ练习

    在前面的文章中,我们已经学习了STL中底层为红黑树结构的一系列关联式容器——set/multiset 和 map/multimap(C++98) 在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次。 在C++11中,

    2024年02月11日
    浏览(43)
  • 【数据结构OJ题】复制带随机指针的链表

    原题链接:https://leetcode.cn/problems/copy-list-with-random-pointer/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 此题可以分三步进行: 1. 拷贝链表的每一个结点,拷贝的结点先链接到被拷贝结点的后面。 2. 复制随机指针的链接:拷贝结点的随机指针指向被拷贝结点随机指针的下

    2024年02月12日
    浏览(70)
  • 单链表OJ题:LeetCode--138.复制带随即指针的链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(68)
  • 尺取法 学习笔记

    尺取法,简单来说是一种利用 双指针法 遍历满足条件的 区间 的算法。 其算法思想为:对数组保存⼀对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。 尺取法不会去枚举到一定不满足条件的区间,所以是一种 ⾼效的枚举

    2024年02月08日
    浏览(40)
  • POJ 2100 Graveyard Design 尺取法

    给出一个数字num,1=num=1e14,找出连续的数字 ai,ai+1...aj使得每一项取平方最后求和等于num,题目要求排列的数字,和排列的个数,输出出来 因为是平方求和,那么我们只需要计算1e7以内的数字就可以,case time limie 2000ms,简单考虑下尺取法最合适,O(n)复杂性,1e7的数组,时间上

    2024年02月09日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包