首页 > 代码库 > UVa1617 Laptop (贪心)

UVa1617 Laptop (贪心)

2024-08-14 10:08:43   217人阅读

链接：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 (贪心)


联系
我们