首页 > 代码库 > UVa1617 Laptop (贪心)
UVa1617 Laptop (贪心)
链接:http://vjudge.net/problem/UVA-1617
分析:先把每个区间按右端点从小到大排序,再按左端点从小到大排序。
贪心策略:
从左边开始取,首先取第一个区间的右端点,然后在第二个区间里取点时分为3种情况:
1)条件:第二个区间的右端点和第一个区间的右端点相同。策略:此时可以将两个区间的线段调整为相邻的,其实就是将第一个区间中的线段向前挪一个位置给第二个区间中的线段腾出空间。
2)条件:第二个区间的左端点大于第一个区间的右端点。策略:此时中间肯定有空隙,标记加1,然后把第二个区间中的线段放置在右端点处。
3)条件:第二个区间的左端点小于等于第一个区间的右端点。策略:此时相当于第一个区间的延伸,我们希望空隙数目最小,所以贪心的紧挨着第一个区间中的线段放一个,此时线段位置为第一个区间线段位置加1(用线段的右端点表示线段位置)。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 100000 + 5; 6 7 struct Interval { 8 int l, r; 9 bool operator < (const Interval& rhs) const {10 return r < rhs.r || (r == rhs.r && l < rhs.l);11 }12 } itv[maxn];13 14 int n;15 16 int main() {17 int T;18 scanf("%d", &T);19 while (T--) {20 scanf("%d", &n);21 for (int i = 0; i < n; i++) scanf("%d%d", &itv[i].l, &itv[i].r);22 sort(itv, itv + n);23 int ans = 0;24 int curPos = itv[0].r;25 for (int i = 1; i < n; i++) if (curPos != itv[i].r) {26 if (curPos < itv[i].l) { ans++; curPos = itv[i].r; }27 else curPos++;28 }29 printf("%d\n", ans);30 }31 return 0;32 }
UVa1617 Laptop (贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。