代码详解
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
/**
* @param n表示区域数目
* @param m表示马路长度
* @seg[N] 用一个pair来维护一个区间
*/
int n, m;
PII seg[N];
int main() {
scanf("%d%d", &m, &n);
for (int i = 0; i < n; ++ i) {
scanf("%d%d", &seg[i].first, &seg[i].second);
}
// 按照区域的first来对区间进行排序
sort(seg, seg + n);
// 马路长度加1,可以在做两数相减的时候不加1
int res = m + 1;
int st = seg[0].first, ed = seg[0].second;
for (int i = 1; i < n; ++ i) {
if (seg[i].first <= ed) ed = max(seg[i].second, ed);
else {
res -= ed - st + 1;
st = seg[i].first, ed = seg[i].second;
}
}
// 最后一组区间会被少计算一次
res -= ed - st + 1;
printf("%d\n", res);
return 0;
}
python 解法
# https://www.acwing.com/problem/content/424/
if __name__ == "__main__":
arr = []
n, m = map(int, input().split())
for _ in range(m):
l, r = map(int, input().split())
arr.append([l, r])
arr.sort()
res = n + 1
start = arr[0][0]
end = arr[0][1]
for i in range(1, m):
if arr[i][0] <= end:
end = max(arr[i][1], end)
else:
res -= end - start + 1
start = arr[i][0]
end = arr[i][1]
res -= end - start + 1
print(res)
可以的!!!
大佬,pair一定要从0开始吗,我从1开始 就错了,改成0就对了
不一定哦,你要是从1开始的话 for(int i = 2; i <= n; i) i就要是等于n,输入为for(int i = 1; i <= n; i) i也要等于n才行
我写的就是后面那种形式for(int i=1;i<=n;i++) 前后一致的,但就是不对 orz
要是从1开始
输入为for(int i=1;i<=n; i)
对区间判断的循环要for(int i=2;i<=n;i)才行。你再试一下或者打印整个数组了解看一下问题
我刚试了一下,如果从1开始的话,sort的长度要变成q+n+1,不然会有1个没排序,