首页 > 代码库 > 区间型贪心总结(1)
区间型贪心总结(1)
1.选择不相交区间。数轴上有n个开区间(ai,bi)。尽量选择多个区间,使得这些区间两两没有公共点。
a.对区间进行排序,排序成b1<=b2<=b3<=.....的形式
b.第一个区间一定要选!
c.
Case 1: a1 > a2 这种情况下选择1区间
Case 2: 排除Case 1后,一定有a1<=a2<=a3<=....., 此种情况应该选1区间,因为此时最优
题目:1214(CODEVS)
下面给出源码
1 //洛谷1214 线段覆盖 2 //区间型贪心 3 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 struct phase { 8 int right, left; 9 }; 10 bool compare(phase a, phase b) { 11 return a.left <= b.left ; 12 } 13 int main() { 14 int n; 15 cin >> n; 16 phase *a = new phase[n]; 17 18 for(int i = 0; i < n; i++) { 19 int r, l; 20 cin >> r >> l; 21 a[i].right = r <= l ? r : l; 22 a[i].left = r > l ? r : l; 23 } 24 25 sort(a, a + n, compare); 26 int ans = 0; 27 int x = a[0].left ; 28 29 for(int i = 1 ; i < n; i++) { 30 if(a[i].right >= x) { 31 ans++, x = a[i].left; 32 } 33 } 34 35 cout << ans + 1 << endl; 36 return 0; 37 38 }
区间型贪心总结(1)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。