CCF买菜

思路

方法一：
归并排序的改造，遇到不相交区间时直接相加，否则依次递增寻找相交子区间长度

#include 
using namespace std;
const int maxn = 2005;
struct node {int x, y;
} a[maxn], b[maxn];
int n, ans;
int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].x, &a[i].y);for(int i = 1; i <= n; i++) scanf("%d %d", &b[i].x, &b[i].y);int i = 1, j = 1;while(i <= n && j <= n) {if(a[i].y <= b[j].x) i++;else if(b[j].y <= a[i].x) j++;else if(a[i].y >= b[j].y) {int k = j;while(k <= n && b[k].x < a[i].y) ans += max(0, min(a[i].y, b[k].y) - max(a[i].x, b[k].x)), k++;i = i + 1;} else {int k = i;while(k <= n && b[j].x < a[k].y) ans += max(0, min(a[k].y, b[j].y) - max(a[k].x, b[j].x)), k++;j = j + 1;}}printf("%d", ans);return 0;
}

方法二：
构造长度为maxn的数组标志某一时刻是否有人装车即可，当遇到一个人在装车，将对应值加一，最后统计值为2的个数

#include 
using namespace std;
const int maxn = 1000005;
int a[maxn], n, ans;
int main() {scanf("%d", &n);for(int i = 0; i < 2; i++) {for(int j = 1, x, y; j <= n; j++) {scanf("%d %d", &x, &y);for(int k = x + 1; k <= y; k++) ans += ++a[k] == 2;}}printf("%d", ans);return 0;
}

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