USACO silver 18 JAN T1

题目链接

http://www.usaco.org/index.phppage=viewproblem2&cpid=786

思路

先按照开始时间从小到大排序，把总覆盖时间求出来
在用第二个for循环把最小单独覆盖的求出来

#include
//#define long long int
using namespace std;
const int N = 1e5+5;
struct node{int l,r;
}line[N];
int n;
bool cmp(node a, node b){if (a.l != b.l) return a.l < b.l;return a.r < b.r;
}
int main(){freopen ("lifeguards.in","r",stdin);freopen ("lifeguards.out","w",stdout);cin >> n;for (int i = 1; i <= n; i++){cin >> line[i].l >> line[i].r;}sort(line+1,line+1+n,cmp);int last = line[1].l, ans = 0;for (int i = 1; i <= n; i++){//这个for求出总覆盖时间 if (line[i].r > last){if (last > line[i].l){ans += line[i].r-last;last = line[i].r;}else{ans += line[i].r-line[i].l;last = line[i].r;}}}last = line[1].l;line[n+1].l = line[n].r;			//设定边界 int m;for (int i = 1; i <= n; i++){//找出自己一个人工作时间最小的人 if (line[i].r < last){m = 0;}else{int p = max(0,min(line[i].r,line[i+1].l) - max(line[i].l, last));last = max(last, line[i].r);m = min(m,p);}}cout << ans-m;
}

反思

碰到这类问题画图来想会比较清楚

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！