本文主要是介绍洛谷P1803 凌乱的yyy / 线段覆盖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:洛谷P1803 凌乱的yyy / 线段覆盖
程序说明:
贪心算法的区间调度问题,在可选工作中,每次都选取结束时间最早的工作。将所有工作按结束时间从小到大排序,若时间不重叠则选取。
注意自定义结构体排序的操作。
此题的大坑!!结构体名不能用time。。因为这个原因导致编译不能通过。。。
代码如下:
#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
struct point {int x, y;
} p[MAX];
bool cmp(point t1, point t2) {return t1.y < t2.y;
}
int n, cnt = 1;
int main() {cin>>n;for(int i = 0; i < n; i++)cin>>p[i].x>>p[i].y;sort(p, p + n, cmp);point t = p[0];for(int i = 1; i < n; i++) {if(p[i].x >= t.y) {cnt++;t = p[i];} }cout<<cnt;return 0;
}
这篇关于洛谷P1803 凌乱的yyy / 线段覆盖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!