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函数与算法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之理解Redis回收算法LRU案例讲解

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

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

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

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

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

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

  • 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蓝桥杯实现线段和点

    目录 一.算法提高 线段和点 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 ,我看网上的人多数用的是c语言.有更好的方法希望可以分享一下下. 1.      有50枚硬币,可能包括4种类型:1元,5角,1角,5分.已知总价值为20元.求各种硬币的数量. 比如:2,34,6,8 就是一种答案. 而 2,33,15,0 是另一个可能的答案,显然答案不唯一. 你的任务是确定类似这样的不同的方案一共有多少个(包括已经给出的2个)? { 可以看出这里的硬币数量和存在着 1元

  • 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中BM(Boyer-Moore)算法的图解与实现

    目录 简介 基本概念 坏字符 好后缀 工作过程 坏字符 好后缀 BM算法 代码实现 最后 简介 本篇文章主要分为两个大的部分,第一部分通过图解的方式讲解BM算法,第二部分则代码实现一个简易的BM算法. 基本概念 bm是一个字符串匹配算法,有实验统计,该算法是著名kmp算法性能的3-4倍,其中有两个关键概念,坏字符和好后缀. 首先举一个例子 需要进行匹配的主串:a b c a g f a c j k a c k e a c 匹配的模式串:a c k e a c 坏字符 如下图所示,从模式串最后一个

  • java 中平方根(sqrt)算法 的实例详解

    java 中平方根(sqrt)算法 平方根(sqrt, square root)是数学中常见的数学的公式; 使用程序进行求平方根主要分为两步: 第一步: while()循环, 控制循环次数及小数的位数, 防止无限循环和出现多位小数; 第二步: 通过分解平方根, 使用循环, 逐渐减小,接近平方根; 同理, 其他方根也可以类似扩展, 不过需要注意的是, 偶数次方根需要确保输入正数; 奇数次方根需要转换为正数, 确保循环收敛, 再进行结果正负判断; 代码如下: /* * Algorithms.java

  • 基于Java实现的Dijkstra算法示例

    本文以实例形式介绍了基于Java实现的Dijkstra算法,相信对于读者研究学习数据结构域算法有一定的帮助. Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法.即先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止. 其代码实现如下所示: package com.algorithm.impl; public class Dijkstra { private static int M =

  • java实现选择排序算法

    java实现选择排序算法

    java实现选择排序算法 public static void selectSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } Sort.swap(array, i, min);//交换i和min } } 选择排序

随机推荐