Java蓝桥杯实现线段和点

目录
  • 一、算法提高 线段和点
    • 1、时间限制
    • 2、问题描述　
    • 3、输入格式
    • 4、输出格式　
    • 5、数据规模和约定　

一、算法提高 线段和点

1、时间限制

1.0s 内存限制：256.0MB

2、问题描述　

有n个点和m个区间，点和区间的端点全部是整数，对于点a和区间[b,c]，若a>=b且a<=c，称点a满足区间[b,c]。
　　求最小的点的子集，使得所有区间都被满足。

3、输入格式

第一行两个整数n m
　　以下n行 每行一个整数，代表点的坐标
　　以下m行 每行两个整数，代表区间的范围

4、输出格式　

输出一行，最少的满足所有区间的点数，如无解输出-1。
样例输入：
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9

样例输出：
2

5、数据规模和约定　

1<=n,m<=10000
　　0<=点和区间的坐标<=50000

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;

public class xianduanhedian {
 private static InputStream is = System.in;

 public static int nextInt() {
  try {
   int i;

   while ((i = is.read()) < 45 || i > 57) {
   }

   int mark = 1, temp = 0;

   if (i == 45) {
    mark = -1;
    i = is.read();
   }

   while (i > 47 && i < 58) {
    temp = temp * 10 + i - 48;
    i = is.read();
   }

   return temp * mark;
  } catch (IOException e) {
   e.printStackTrace();
  }

  return -1;
 }

 static class Node {
  public int start;
  public int end;

  public Node(int start, int end) {
   this.start = start;
   this.end = end;
  }

 }

 public static void main(String[] args) {
  int n = nextInt();
  int m = nextInt();
  int point[] = new int[n];
  for (int i = 0; i < n; i++)
   point[i] = nextInt();
  Node node[] = new Node[m];
  for (int i = 0; i < m; i++)
   node[i] = new Node(nextInt(), nextInt());
  Arrays.sort(point);
  Arrays.sort(node, new Comparator<Node>() {
   public int compare(Node o1, Node o2) {
    return o1.end - o2.end;
   }
  });
  int currentPoint = 0;
  int count = 0;
  int j = 1;
  for (int i = 0; i < m; i++) {
   int x = node[i].start;
   int y = node[i].end;
   if (x <= currentPoint)
    continue;
   int temp = -1;
   for (j -= 1; j < n; j++) {
    if (point[j] <= y) {
     temp = point[j];
    } else {
     break;
    }
   }
   if (temp == -1) {
    count = 0;
    break;
   } else {
    currentPoint = temp;
    count++;
   }

  }
  System.out.println(count);
 }

}

到此这篇关于Java实现蓝桥杯 算法提高 线段和点的文章就介绍到这了,更多相关Java内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java DFA算法案例详解

    Java DFA算法案例详解

    1.背景 项目中需要对敏感词做一个过滤,首先有几个方案可以选择: 直接将敏感词组织成String后,利用indexOf方法来查询. 传统的敏感词入库后SQL查询. 利用Lucene建立分词索引来查询. 利用DFA算法来进行. 首先,项目收集到的敏感词有几千条,使用a方案肯定不行.其次,为了方便以后的扩展性尽量减少对数据库的依赖,所以放弃b方案.然后Lucene本身作为本地索引,敏感词增加后需要触发更新索引,并且这里本着轻量原则不想引入更多的库,所以放弃c方案.于是我们选定d方案为研究目标. 2.

  • java算法入门之有效的括号删除有序数组中的重复项实现strStr

    java算法入门之有效的括号删除有序数组中的重复项实现strStr

    目录 1.LeetCode 20.有效的括号 题目 小编菜解 思路及算法 大神解法 2.LeetCode 26.删除有序数组中的重复项 题目 小编菜解初版 小编菜解改进版 思路及算法 大神解法 3.LeetCode 28.实现strStr 题目 小编菜解 大神解法 也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1

  • 每天练一练Java函数与算法Math函数总结与字符串转换整数

    题目 请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数). 函数 myAtoi(string s) 的算法如下: 读入字符串并丢弃无用的前导空格 . 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有). 确定最终结果是负数还是正数.如果两者都不存在,则假定结果为正. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾.字符串的其余部分将被忽略. 将前面步骤读入的这些数字转换为整数

  • Java面试题冲刺第二十三天--算法(2)

    Java面试题冲刺第二十三天--算法(2)

    目录 面试题1:你说一下常用的排序算法都有哪些? 追问1:谈一谈你对快排的理解吧 追问2:说一下快排的算法原理 追问3:来吧!给我手敲一个快排 面试题2:来!再给我手撸一个Spring 追问1:哦,咳咳-说一下构成递归的前提条件有啥? 追问2:递归都有哪些优缺点? 追问3:给我手写一个简单的递归算法的实现吧 面试题3: 10亿个数中找出最大的100000个数(top K问题) 总结 面试题1:你说一下常用的排序算法都有哪些? 追问1:谈一谈你对快排的理解吧 快速排序,顾名思义就是一种以效率快为特

  • Java红黑树的数据结构与算法解析

    Java红黑树的数据结构与算法解析

    目录 红黑树的介绍 红黑树的实现 1.节点 2.查找 3.平衡化 颜色反转 插入的实现 红黑树的复杂度– 总结 红黑树的介绍 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树. 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值. 除了具备该特性之外,红黑树还包括许多额外的信息. 红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black). 红黑树的特性: (1)

  • Java面试题冲刺第二十天--手撸算法

    目录 手撸算法1:查找数组中重复元素和重复元素的个数 1. 两层循环比较方式 2. 转成Map集合处理方式 手撸算法2:写个二分查找demo吧 手撸算法3:把两个有序数组合并成一个有序数组 总结 手撸算法1:查找数组中重复元素和重复元素的个数 当听让我写这个算法时,纸笔还没给到我手上,作为一个资深MySQL爱好者,瞬间从裤裆掏出一杆笔,打个哈欠的功夫,就在面试官脸上写下了: select num,count(num) from T group by num order by count(num)

  • Java之理解Redis回收算法LRU案例讲解

    如何通俗易懂的理解LRU算法? 1.LRU是什么? LRU全称Least Recently Used,也就是最近最少使用的意思,是一种内存管理算法,最早应用于Linux操作系统. LRU算法基于一种假设:长期不被使用的数据,在未来被用到的几率也不大.因此,当数据所占内存达到一定阈值时,我们要移除掉最近最少被使用的数据. LRU算法应用:可以在内存不够时,从哈希表移除一部分很少访问的用户. LRU是什么?按照英文的直接原义就是Least Recently Used,最近最久未使用法,它是按照一个非

  • Java蓝桥杯实现线段和点

    目录 一.算法提高 线段和点 1.时间限制 2.问题描述 3.输入格式 4.输出格式 5.数据规模和约定 一.算法提高 线段和点 1.时间限制 1.0s 内存限制:256.0MB 2.问题描述 有n个点和m个区间,点和区间的端点全部是整数,对于点a和区间[b,c],若a>=b且a<=c,称点a满足区间[b,c]. 求最小的点的子集,使得所有区间都被满足. 3.输入格式 第一行两个整数n m 以下n行 每行一个整数,代表点的坐标 以下m行 每行两个整数,代表区间的范围 4.输出格式 输出一行,最

  • java蓝桥杯历年真题及答案整理(小结)

    蓝桥杯java历年真题及答案整理(闭关一个月,呕心沥血整理出来的) 1 全排列 是这样的,如果给定N个不同字符,将这N个字符全排列,最终的结果将会是N!种.如:给定 A.B.C三个不同的字符,则结果为:ABC.ACB.BAC.BCA.CAB.CBA一共3!=3*2=6种情况. package Question1_9; import java.util.Scanner; import java.util.Vector; public class Question1 { public static

  • java蓝桥杯试题

    因为要参加蓝桥杯,琢磨了一下算法,原来数学不好是这么难搞:下面是一些蓝桥杯的试题(习题).我用的是java ,我看网上的人多数用的是c语言.有更好的方法希望可以分享一下下. 1.      有50枚硬币,可能包括4种类型:1元,5角,1角,5分.已知总价值为20元.求各种硬币的数量. 比如:2,34,6,8 就是一种答案. 而 2,33,15,0 是另一个可能的答案,显然答案不唯一. 你的任务是确定类似这样的不同的方案一共有多少个(包括已经给出的2个)? { 可以看出这里的硬币数量和存在着 1元

  • Java实现蓝桥杯 算法提高 线段和点

    目录 一.算法提高 线段和点 1.时间限制 2.问题描述 3.输入格式 4.输出格式 5.数据规模和约定 一.算法提高 线段和点 1.时间限制 1.0s 内存限制:256.0MB 2.问题描述 有n个点和m个区间,点和区间的端点全部是整数,对于点a和区间[b,c],若a>=b且a<=c,称点a满足区间[b,c]. 求最小的点的子集,使得所有区间都被满足. 3.输入格式 第一行两个整数n m 以下n行 每行一个整数,代表点的坐标 以下m行 每行两个整数,代表区间的范围 4.输出格式 输出一行,最

  • C++实现蓝桥杯竞赛题目---搭积木

    C++实现蓝桥杯竞赛题目---搭积木

    小明对搭积木非常感兴趣.他的积木都是同样大小的正立方体. 在搭积木时,小明选取 m 块积木作为地基,将他们在桌子上一字排开,中间不留空隙,并称其为第0层. 随后,小明可以在上面摆放第1层,第2层,--,最多摆放至第n层.摆放积木必须遵循三条规则 规则1:每块积木必须紧挨着放置在某一块积木的正上方,与其下一层的积木对齐: 规则2:同一层中的积木必须连续摆放,中间不能留有空隙: 规则3:小明不喜欢的位置不能放置积木. 其中,小明不喜欢的位置都被标在了图纸上.图纸共有n行,从下至上的每一行分别对应积木

  • Java实现蓝桥杯G将军的示例代码

    G将军有一支训练有素的军队,这个军队除开G将军外,每名士兵都有一个直接上级(可能是其他士兵,也可能是G将军).现在G将军将接受一个特别的任务,需要派遣一部分士兵(至少一个)组成一个敢死队,为了增加队员的独立性,要求如果一名士兵在队中,他的直接上级不能在队中. 请问,G将军有多少种派出队的方法.注意,G将军也可以作为一个士兵进入队. 输入格式 输入的第一行包含一个整数n,表示包括G将军在内的军队的人数.军队的士兵从1至n编号,G将军编号为1. 接下来n-1个数,分别表示编号为2, 3, -, n的

  • Java实现蓝桥杯数独游戏的示例代码

    Java实现蓝桥杯数独游戏的示例代码

    你一定听说过"数独"游戏. 如图,玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行.每一列.每一个同色九宫内的数字均含1-9,不重复. 数独的答案都是唯一的,所以,多个解也称为无解. 本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目.但对会使用计算机编程的你来说,恐怕易如反掌了. 本题的要求就是输入数独题目,程序输出数独的唯一解.我们保证所有已知数据的格式都是合法的,并且题目有唯一的解. 格式要求: 输入9行,每行9个数字,0代表未知,其它数字为

  • 跟我学Java Swing之游戏设计(1)

    文章来源:电脑爱好者 作者:张剑 谁知道通天的巴比伦塔耗费了多少沙石?又有谁知道罗马的建成经历了多少个日夜?我们惟一知道的是,没有一块块砖石的垒砌,就没有蜿蜒万里的长城;没有巨石和黏土的堆集,就没有亘古不变的金字塔.由此可见,基础知识的准备对于我们学习任何事物都至关重要,那么,就让我们从认识Swing的一些基础功能开始,启动我们建造罗马的伟大工程吧! 前言 Java咖啡馆已经开张不少时日了,如果你已经喜欢上了Java这杯咖啡的味道,那么记得常来哦.这一次,我们为大家准备了一大杯香浓的咖啡--将以

  • Python爬虫之对CSDN榜单进行分析

    前言 本篇文章的主要内容是利用Python对CSDN热榜变冷榜的指标数据进行分析的爬虫 分析一下各指标 开始爬取热榜,请稍候...耗时:2.199401808s [Top100指标统计] 浏览为0的:        3评论为0的:       76收藏为0的:       51浏览评论0的:    3三指标都0的:    2 浏览个位数的:    25评论个位数的:    98收藏个位数的:    86无封面题图的:    74 浏览>=100的:    18评论>=10的:      1收藏

  • C++数组放在main函数内外的区别

    C++数组放在main函数内外的区别

    目录 思路 错误代码 正确代码 问题分析 总结 先来看一道小题,第十届蓝桥杯省赛C++/B组填空题第三题 试题 C:数列求值 本题总分:10 分 [问题描述] 给定数列 1, 1, 1, 3, 5, 9, 17, …,从第 4 项开始,每项都是前 3 项的和.求第 20190324 项的最后 4 位数字. [答案提交] 这是一道结果填空的题,你只需要算出结果后提交即可.本题的结果为一 个 4 位整数(提示:答案的千位不为 0),在提交答案时只填写这个整数,填写多余的内容将无法得分. 思路 显然,

随机推荐