小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。
这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[xi,yi]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。
输入包括n+1行。第一行包括两个正整数n和L(1<=n<=105,1<=L<=109)接下来的n行,每行两个正整数xi,yi(0<=xi<=yi<=109),表示第i个真视守卫覆盖的区间。
一个整数,表示最少需要的真视守卫数量, 如果无解, 输出-1。
4 6 3 6 2 4 0 2 4 7
3
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int L=in.nextInt(); int[][] temp=new int[n][2]; for(int i=0;i<n;i++) { for(int j=0;j<2;j++) { temp[i][j]=in.nextInt(); } } //。获得了数组,进行排序 Arrays.sort(temp,new Comparator<int[]>() { public int compare(int[] o1, int[] o2) { return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]; } }); int index=0; int count=0; int pre=0; //右边界 while(pre<L) { if(temp[index][0]>pre) { System.out.println(-1); } int max=0; while(index<n&&temp[index][0]<=pre) { max=Math.max(max, temp[index][1]); index++; } count++; pre=max; if(pre>=L) { System.out.println(count); return; } if(index>=n) { System.out.println(-1); return; } } } }Java贪心算法
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n,L;cin >> n >> L; vector<pair<int,int>> vec(n); for(int i=0;i<n;++i) cin >> vec[i].first >> vec[i].second; sort(vec.begin(),vec.end()); if(vec[0].first>0) {cout << -1;return 0;}//teshuqingkuang int right = 0; int i = 0; int res = 0; while(i<n){ int r = right; for(;i<n && vec[i].first<=r;++i){ right = max(right,vec[i].second); } ++res; if(right>=L) {cout << res;return 0;} if(i>=n || vec[i].first>right) {cout << -1;return 0;} } return 0; }
import sys n, L = [int(x) for x in input().strip().split()] regions = [] for row in sys.stdin: regions.append([int(x) for x in row.strip().split()]) regions.sort(key=lambda x: x[0]) pre_end = 0 res = 0 i = 0 while i < len(regions): if regions[i][0] > pre_end: res = -1 break k = i + 1 cur_end = regions[i][1] while k < len(regions) and regions[k][0] <= pre_end: cur_end = max(cur_end, regions[k][1]) k += 1 pre_end = cur_end i = k res += 1 if pre_end >= L: break if pre_end < L: res = -1 print(res)
//贪心选择 n,L = map(int,input().split()) xy = [] for _ in range(n): xy.append(list(map(int,input().split()))) xy.sort(key = lambda x : x[0]) last = 0//当前已选尾部位置 max_reach = 0//当前可选最大到达位置 cnt = 1//ans 先加最后一个 for i in range(n): if max_reach >=L:break//一定要加,不然初始化1可能会重复 if xy[i][0]>max_reach: print(-1) exit() if xy[i][0]>last://此时需要更新last last = max_reach//确定选择max_reach cnt+=1 max_reach = max(xy[i][1],max_reach)//勿忘更新max continue max_reach = max(xy[i][1],max_reach)//日常更新max if max_reach >= L: print(cnt) else: print(-1)
#include <bits/stdc++.h> using namespace std; int main() { long long l, n; cin >> n; cin >> l; vector<pair<long long, long long>> data(n); for (int i = 0; i < n; i++) { cin >> data[i].first; cin >> data[i].second; } sort(data.begin(), data.end(), [](pair<long long, long long> left, pair<long long, long long> right) { if (left.first == right.first) return left.second > right.second; else return left.first < right.first; }); int res = 0; long long right = -1; int index = 0; while (right < l && index < n) { long long lastRight = right; //贪心 寻找可以到达的最远距离 while (index < n && data[index].first <= lastRight + 1) { right = max(data[index].second, right); index++; } //无法到达比 lastRight更远的距离 if (right == lastRight) break; //只要right更新 就代表又选择了 一个真视守卫 res++; } if (right < l) cout << -1; else cout << res; }
#include <iostream> #include <map> using namespace std; class Solution{ public: void leastCoverdRiver(){ multimap<int,int> nums; int n,L,a,b; cin>>n>>L; for(int i=0;i<n;i++){ cin>>a>>b; nums.insert(multimap<int,int>::value_type(a,b)); } if(L==0){ cout<<-1<<endl; return; } int ans=1,l=0,r=nums.begin()->second;;//初始化已经有1个 for(auto& num:nums){ //判断左边界已经进入下一个阶段,需满足大于之前的边界 if(l<num.first&&num.second>r){l=r;ans++;} if(num.first<=l&&num.second>r){//选出最大的右边界 r=num.second; } if(r>=L) break;//满足条件退出 } if(r>=L){//判断是否在该区域内 cout<<ans<<endl; }else{ cout<<-1<<endl; } } }; int main(int argc,char* argv[]){ Solution().leastCoverdRiver(); return 0; }利用map即可,默认按照key升序排序,每次枚举记下右边界L最大值,并且判断是否在允许的左边界R内,若满足,则更新最大的右边界面,否则,则更新左边界,并进行计数。
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int l = scanner.nextInt(); PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> { if (o1[0] == o2[0]) return o2[1] - o1[1]; return o1[0] - o2[0]; }); for (int i = 0; i < n; i++) { int[] arr = new int[2]; arr[0] = scanner.nextInt(); arr[1] = scanner.nextInt(); queue.offer(arr); } scanner.close(); if (queue.peek()[0] != 0) { System.out.println(-1); } else { int from = queue.poll()[1]; int count = 1; PriorityQueue<int[]> queue1 = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]); while (from < l) { while (queue.size() > 0 && queue.peek()[0] <= from) queue1.offer(queue.poll()); if (queue1.size() > 0 && queue1.peek()[1] > from) { from = queue1.poll()[1]; count++; } else { System.out.println(-1); return; } } System.out.println(count); } } }
import java.util.*; public class Main{ public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int l = in.nextInt(); int[][] guard = new int[n][2]; for (int i = 0;i < guard.length; ++i) { guard[i][0] = in.nextInt(); guard[i][1] = in.nextInt(); } Arrays.sort(guard, (a, b) -> a[0]-b[0]); if (guard[0][0] > 0) System.out.println(-1); int end = guard[0][1]; int cnt = 1; int max = end; for (int i = 1;i < guard.length; ++i) { if (guard[i][0] <= end) { max = Math.max(max, guard[i][1]); } else { if (guard[i][0] > max) System.out.println(-1); else { end = max; max = guard[i][1]; cnt++; } } if (end >= l) { System.out.println(cnt); return; } } if (end != max){ end = max; cnt++; } if (end >= l) { System.out.println(cnt); } else { System.out.println(-1); } } }
# include <iostream> # include <cstdlib> # include <stack> # include <cstring> # include <unordered_map> # include <vector> # include <algorithm> # define N 100100 # define inf 0x3f3f3f3f using namespace std; int n,L; int main(void){ while( cin>>n>>L ){ vector<vector<int>> nums; int a,b; for ( int i=0; i<n; ++i ){ cin>>a>>b; nums.push_back({a,b}); } sort( nums.begin(), nums.end(), [](vector<int>&a, vector<int>&b){ return a[0]<b[0] || (a[0]==b[0] && a[1]>b[1]); } ); int pre = 0, i=0, ans=0, last=0; while( i<nums.size() ){ while( i<nums.size() && nums[i][0]<=pre ){ last = max(last, nums[i][1]); ++i; } ++ans; pre = last; if ( i<nums.size() && nums[i][0]>pre ){ ans = -1; break; } if ( last>=L ) break; } if ( ans==-1 || last<L ) cout<<-1<<endl; else cout<<ans<<endl; } return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int L = in.nextInt(); int[][] arr = new int[n][2]; for(int i =0;i<n;i++){ for(int j =0;j<2;j++){ arr[i][j] = in.nextInt(); } } //贪心思想,每次找右边值能覆盖最大范围,所用个数最小 //按左边值排序 Arrays.sort(arr, (int[] o1,int[] o2)-> o1[0]-o2[0]); int rowIndex = 1; int count = 1; //第一个值存起来,后面的遍历与这个比较 int[] temp = arr[0]; //保存右边值得最大值, int maxValue = temp[1]; //如果开头不为0则返回-1 if (temp[0] != 0){ System.out.println(-1); return; } while(rowIndex<arr.length){ //如果右边最大值超过L则说明覆盖完全,++count是因为要加上maxValue这个守卫 if(maxValue >=L){ System.out.println(++count); return; } //最开始的右边值覆盖不住左边值时,说明要换守卫,所以守卫加一,并更新右边值 if(arr[rowIndex][0] > temp[1]){ count++; temp[1] = maxValue; }else{ maxValue = Math.max(maxValue,arr[rowIndex][1]); rowIndex++; } } //如果符合条件的在最后一个,则maxValue此时就是能够覆盖的值,所以需要再进行判断 if(maxValue >=L){ System.out.print(++count); }else{ //如果都没有符合条件的值,同样会遍历完 System.out.print(-1); } } }
package main import "fmt" import "sort" func covered(nums [][]int, length int) int { sort.Slice(nums,func(i, j int) bool { if nums[i][0] == nums[j][0] { return nums[i][1] > nums[j][1] } else { return nums[i][0] < nums[j][0] } }) pre_end := 0 start := 0 res := 0 for start < len(nums) { if nums[start][0] > pre_end { return -1 } k := start + 1 max := nums[start][1] for k < len(nums) && nums[k][0] <= pre_end { if max < nums[k][1] { max = nums[k][1] } k++ } pre_end = max res++ start = k if pre_end >= length { break } } if pre_end < length { return -1 } return res } func main() { var n, l int fmt.Scanln(&n,&l) var a,b int nums := [][]int{} for i := 0; i < n; i++ { fmt.Scanln(&a,&b) nums = append(nums, []int{a,b}) } ans := covered(nums,l) fmt.Println(ans) } 无论如何都只过60%是怎么回事啊?求大佬带教教我
该题关键是要完全覆盖河道.
我们可以将覆盖区间的起始点从小到大排序, 若起始点相同,那么在根据结束点排序.
我们只需从左往右看, 在目前能到达的长度下, 尽可能挑选一个照的远的眼. 当眼的起始点已经超过目前能到达的长度时
眼数 + 1
#include <algorithm> #include <iostream> #include <stack> #include <vector> using namespace std; class Solution { public: }; struct Comparator { // 我们可以将覆盖区间的起始点从小到大排序, 若起始点相同,那么在根据结束点排序. bool operator()(pair<int, int> p1, pair<int, int> p2) { if (p1.first == p2.first) return p1.second < p2.second; else return p1.first < p2.first; } } comparator; int main() { int n, l; cin >> n >> l; pair<int, int> sections[100000]; for (int i = 0; i < n; ++i) { cin >> sections[i].first >> sections[i].second; } // 排序 sort(sections, sections + n, comparator); int i = 0; int newLength = 0; // 去除被完全覆盖的区间 如 [0, 9], [0, 8]其中[0, 8]是不可能选择的, 要尽可能少买眼, 所以只用考虑照亮区间大的 while (i < n) { int val = sections[i].first; while (val == sections[i].first) { ++i; } sections[newLength++] = sections[i - 1]; } // 若连最开始的眼都找不了开头, 那不可能完全覆盖 if (sections[0].first > 0) { cout << "-1"; return 0; } // 更新区间数组长度 n = newLength; i = 0; // 要买的眼数 int output = 0; // 未来可以到达的长度 int tail = sections[0].second; // 目前可以到达的长度 int last = -1; while (i < n) { // 在可以到达的长度时, 尽可能选择能照更远的 while (i < n && sections[i].first <= last) { tail = max(tail, sections[i].second); ++i; } // 目前sections[i] 已经超过目前可以到达的长度, 逼不得已买一个眼, 这个眼就是之前`尽可能选择能照更远的`的眼 ++output; last = tail; // 若目前能到达的长度已经超过l, 可以完全覆盖 if (last > l) { cout << output; return 0; } // 不连续, 不能完全覆盖 if (sections[i].first > tail) { cout << "-1"; return 0; } } // 区间用完了, 但若目前能到达的长度也到达不了l if (tail < l) cout << "-1"; }
#include<vector> #include<iostream> #include<algorithm> using namespace std; int main(){ int n, L; cin >> n >> L; vector<vector<int>> spans(n,vector<int>(2,0)); for(int i =0; i < n; i++){ cin >> spans[i][0] >> spans[i][1]; } sort(spans.begin(), spans.end()); int ans = 0; // 贪心算法 int l = 0, r = 0; int left = 0, right = n - 1; // bool ok = false; while(left <= right){ int i = left; while(i <= right && spans[i][0] <= l && r < L){ r = max(r, spans[i][1]); i ++; } l = r; if(r >= L){ cout << ans + 1<< endl; return 0; } if(left == i){ cout << -1 << endl; return 0; } ans ++; left = i; } cout << -1 << endl; return 0; }
package main import ( "fmt" "sort" "bufio" "strings" "strconv" "os" ) type pair struct{ a,b int } func main(){ var n,l int fmt.Scan(&n,&l) inp:=bufio.NewReader(os.Stdin) li:=make([]pair,n) for i:=0;i<n;i++{ str,_:=inp.ReadString('\n') str_l:=strings.Split(str[:len(str)-1]," ") li[i].a,_=strconv.Atoi(str_l[0]) li[i].b,_=strconv.Atoi(str_l[1]) } sort.Slice(li,func(i,j int)bool{ if li[i].a!=li[j].a{ return li[i].a<li[j].a }else{ return li[i].b>li[j].b } }) r:=0 con:=0 id:=0 for r<l{ if li[id].a>r{ fmt.Println(-1) return } p:=0 for ;id<n&&li[id].a<=r;id++{ p=max(p,li[id].b) } r=p con++ if r>=l{ fmt.Println(con) return } if id>=n{ fmt.Println(-1) return } } } func max(a,b int)int{ if a>b{ return a } return b }
// 贪心法即可解决这个问题 #include<iostream> #include<queue> using namespace std; int main() { int n, L, l, r, res = 0, max_step = 0; cin >> n >> L; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pQue;; for(int i = 0; i < n; ++i) { cin >> l >> r; pQue.push({l, r}); } while(max_step < L && !pQue.empty()) { int tmp = max_step; while(!pQue.empty() && pQue.top().first <= max_step) { tmp = max(tmp, pQue.top().second); pQue.pop(); } if(tmp <= max_step) break; else { max_step = tmp; res += 1; } } if(max_step >= L) cout << res << endl; else cout << -1 << endl; return 0; }
n, L = [int(x) for x in input().split()] nums = [] while(n>0): n -= 1 tmp = [int(x) for x in input().split()] nums.append(tmp) nums.sort(key=lambda x: (x[0], -1*x[1])) pre_end = nums[0][1] ans = [nums[0]] cover_max = 0 i = 1 while i < len(nums): start, end = nums[i][0], nums[i][1] if start <= pre_end: cover_tmp = end - pre_end if cover_max < cover_tmp: i_select = i cover_max = cover_tmp i += 1 else: ans.append(nums[i_select]) pre_end = nums[i_select][1] cover_max = 0 if pre_end >= L: break if pre_end < L: ans.append(nums[i_select]) if ans[-1][1]>= L: print(len(ans)) else: print(-1)
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int size = sc.nextInt(); int length = sc.nextInt(); int[][] guard = new int[size][2]; for(int i = 0;i < size;i++) { for(int j = 0;j < 2;j++) { guard[i][j] = sc.nextInt(); } } System.out.println(solute(guard,length)); } public static int solute(int[][] guard,int length) { Arrays.sort(guard, (a, b) -> { if(a[0] == b[0]){ return b[1] - a[1]; }else { return a[0] - b[0]; } }); int right = guard[0][1]; int count = 1; for(int i = 0;i < guard.length;i++) { i--; if(right >= length) return count; int max = Integer.MIN_VALUE; while (i + 1 < guard.length && guard[i + 1][0] <= right) { i++; if(guard[i][1] > max) { max = guard[i][1]; } } if(max == Integer.MIN_VALUE) { return -1; } right = max; count++; } return count; } }