Java藍橋杯實現線段和點
一、算法提高 線段和點
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內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- java實現馬踏棋盤遊戲
- Java數據結構之環形鏈表和約瑟夫問題詳解
- Java數據結構與算法入門實例詳解
- java數組算法例題代碼詳解(冒泡排序,選擇排序,找最大值、最小值,添加、刪除元素等)
- Java進階核心之InputStream流深入講解