题目一：1399: 校门外的树

P1399 - 校门外的树 - HAUEOJ

代码

#include<bits/stdc++.h>
using namespace std;using PII = pair<int,int>;
const int N = 1e5+10;
vector<PII>a, b;int main() {int n, m;cin >> n >> m;while(m --) {int l, r;cin >> l >> r;a.push_back({l,r});}sort(a.begin(),a.end()); int cnt = n + 1;int l = -1, r = -1;for(int i = 0; i < a.size(); i ++) {if(a[i].first>r) {if(l!=-1 && r!=-1) b.push_back({l,r});l = a[i].first;r = a[i].second;}r = max(r,a[i].second);}b.push_back({l,r}); // 把最后一个区间放进去 for(auto x : b) {cnt -= x.second-x.first+1;}cout << cnt << endl;return 0;
}

题目二：1343. 挤牛奶

1343. 挤牛奶 - AcWing题库

代码 

不要忘了sort 左端点，还有处理边界细节，开始0到最前面的左端点不算最长无人持续时间。

#include<bits/stdc++.h>
using namespace std;int n;
using PII = pair<int,int>;
const int N = 1e4+10;
vector<PII> a, b;int main() {cin >> n;while(n --) {int l, r;cin >> l >> r;a.push_back({l,r});}sort(a.begin(),a.end()); // 不要忘了排序左端点int l=-1, r=-1;int maxnotime = 0, maxtime = 0;for(int i = 0; i < a.size(); i ++) {if(a[i].first>r) {//maxnotime = max(maxnotime, a[i].first-r);if(l!=-1) {b.push_back({l,r});maxnotime = max(maxnotime, a[i].first-r);}l = a[i].first;r = a[i].second;}r = max(r,a[i].second);}b.push_back({l,r});for(auto x : b) {maxtime = max(maxtime,x.second-x.first);}cout << maxtime << " " << maxnotime << endl;return 0;
}

题目三：1400: 现在是摸鱼时间2.0

P1400 - 现在是摸鱼时间2.0 - HAUEOJ

 

代码 

主要是边界上的考虑。

string 存储端点。PII 存区间

开头st==00：00：00 到第一个区间左端点，第一个需要考虑的边界

末尾st=?max(st,a[i].second) i == a.size()-1, 第二个需要考虑的边界，是否到一天结束

max(st,a[i].second) 是因为要取最右边的，你不知道当前区间右端点是否都比前面的右端点都大，因为排序的是左端点。

#include<bits/stdc++.h>
using namespace std;// 区间和并，合并重叠的时间
// 除去区间内的区域都摸鱼using PSS = pair<string,string>;
int n;
vector<PSS> a;int main() {cin >> n;while(n --) {// string 存储区间端点 string s1, s, s2;cin >> s1 >> s >> s2;a.push_back({s1,s2});}// 排序左端点sort(a.begin(),a.end());// 边界变量定义 string st = "00:00:00";int flag = 1; for(int i = 0; i < a.size(); i ++) {//开头边界处理 if(st=="00:00:00" && a[i].first!="00:00:00") {cout << st << " - " << a[i].first << endl;st = a[i].second; flag = 0;continue;}if(a[i].first<=st) {st = max(st,a[i].second);}else if(a[i].first>st) {cout << st << " - " << a[i].first << endl;st = a[i].second; flag = 0;}// 末尾边界处理 if(i == a.size()-1 && st<"23:59:59") {flag = 0;cout << st << " - " << "23:59:59" << endl;}}if(flag) puts("来世还作程序员!");return 0;
}