#8 wa,想不出来为啥,求大佬看看
  • 板块P1496 火烧赤壁
  • 楼主xjstud
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/18 23:38
  • 上次更新2024/1/19 11:54:42
查看原帖
#8 wa,想不出来为啥,求大佬看看
1238244
xjstud楼主2024/1/18 23:38
#include <stdio.h>

struct ha {
	int l;
	int r;
} kun[40014], hun[40014];
int a = 0;

int haha(int l, int r) {归并排序
	if (l >= r)
		return 0;
	int mid = (l + r) / 2;
	haha(l, mid);
	haha(mid + 1, r);
	int i = l, j = mid + 1, m = 0;
	while (i <= mid && j <= r) {
		if (kun[i].l < kun[j].l)
			hun[m++] = kun[i++];
		else if (kun[i].l < kun[j].l)
			hun[m++] = kun[j++];
		else { //		{为了去重简单的合并}
			if (kun[i].r > kun[j].r)
				kun[j].r = kun[i].r;
			else
				kun[i].r = kun[j].r;
			hun[m++] = kun[j++];
			hun[m++] = kun[i++];
		}
	}
	while (i <= mid)
		hun[m++] = kun[i++];
	while (j <= r)
		hun[m++] = kun[j++];
	m = 0, i = l;
	while (i <= r)
		kun[i++] = hun[m++];
	return 0;
}

heti() { //区间合并
	int j = 1;
	for (int i = 2; i <= a; i++) {
		if (kun[j].r >= kun[i].l)
			kun[j].r = kun[j].r > kun[i].r ? kun[j].r : kun[i].r;
		else {
			kun[++j] = kun[i];
		}
	}

	return j;
}

main() {

	scanf("%d", &a);
	for (int i = 1; i <= a; i++)
		scanf("%d %d", &kun[i].l, &kun[i].r);
	haha(1, a);

	int k = heti();
	int count = 0;
	while (k) {
		count += kun[k].r - kun[k].l;
		k--;
	}
	printf("%d", count);
}
2024/1/18 23:38
加载中...