当前位置: 首页 > article >正文

市长海报/ Mayor‘s posters

AB 省 Bytetown 的市民无法忍受市长竞选活动的候选人随心所欲地将他们的选举海报贴在各个地方。市议会最终决定建造一面选举墙来放置海报,并引入以下规则:
  • 每个候选人都可以在墙上放置一张海报。
  • 所有海报的高度都与墙壁的高度相同;海报的宽度可以是任意整数字节(byte 是 Bytetown 中的长度单位)。
  • 墙被分成几段,每段的宽度为 1 个字节。
  • 每张海报必须完全覆盖连续数量的墙段。

他们建造了一堵 10000000 字节长的墙(这样就有足够的空间容纳所有候选人)。当竞选活动重新开始时,候选人将他们的海报贴在墙上,他们的海报宽度差异很大。此外,候选人开始将他们的海报张贴在已经被其他海报占据的墙面上。Bytetown 的每个人都很好奇,在选举前的最后一天,谁的海报将(全部或部分)可见。
您的任务是根据海报的大小、位置和在选举墙上的放置顺序等信息,找出放置所有海报时可见海报的数量。

输入

输入的第一行包含一个数字 c,给出后面的 case 数。单个案例的第一行数据包含数字 1 <= n <= 10000。随后的 n 行按海报的放置顺序描述海报。n 行中的第 i 行包含两个整数 li 和 ri,分别是第 i 张海报的左端和右端所占据的墙段编号。我们知道,对于每个 1 <= i <= n, 1 <= li <= ri <= 10000000。放置第 i 张海报后,它将完全覆盖编号为 li、li+1 ,... , ri 的所有墙段。

输出

对于每个输入数据集,在放置所有海报后打印可见海报的数量。

下图说明了 sample input 的情况。

样本

输入复制输出复制
1
5
1 4
2 6
8 10
3 4
7 10
4

思路:

 因为范围比较大,所以用离散化将其范围变小,然后在用线段树做题

代码:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct sss {
	int x, y, k;
}a[80005];//线段树
bool b[10005];//判断海报是否访问过
struct ss {
	int x, i;//i 第i个坐标
	bool v;//判断是左边还是右边边界
}c[20005],e[20005];//归并离散化,减少范围
struct s{
	int	x, y;
}d[10005];//离散化后的墙段
int f, n, x, y;
//建立线段树
void bulid(int i,int x, int y) {
	a[i].x = x;
	a[i].y = y;
	a[i].k = 0;
	if (x == y) {
		return;
	}
	int mid = (x + y) / 2;
	bulid(2 * i, x, mid);
	bulid(2 * i + 1, mid + 1, y);
}
//线段树的区间修改
void tianjia(int i, int x, int y, int j) {
	if (a[i].x >= x && a[i].y <= y) {
		a[i].k = j;
		return;
	}
	else if((a[i].x < x && a[i].y >=x)||(a[i].x <=y && a[i].y > y)){
		if (a[i].x == a[i].y) {
			return;
		}
		if (a[i].k != 0) {
			a[i * 2 + 1].k = a[i].k;
			a[i * 2].k = a[i].k;
			a[i].k = 0;
		}
		int mid = (a[i].x + a[i].y) / 2;
		if (mid >= x)
			tianjia(2 * i, x, y, j);
		if (mid < y)
			tianjia(2 * i + 1, x, y, j);
	}
	else {
		return;
	}
}
//清除痕迹
void qingchu(int i) {
	a[i].k = 0;
	if(a[i].x!=a[i].y)
	{
		qingchu(i * 2);
		qingchu(i * 2 + 1);
	}
}
//查询多少海报漏出来
void chazhao(int i,int &q) {
	if (a[i].k != 0) {
		if(b[a[i].k] == false){
			q++;
			b[a[i].k] = true;			
		}
		qingchu( i);
		return;
	}
	else if (a[i].x == a[i].y) {
		return;
	}
	else {
		chazhao(i * 2, q);
		chazhao(i * 2 + 1, q);
	}
}
//归并排序
void guibing(int i, int j) {
	if (i >= j) {
		return;
	}
	int mid = i + (j - i) / 2;
	guibing(i, mid);
	guibing(mid + 1, j);
	int r = i, l = mid + 1, h = i;
	while (r <= mid && l <= j) {
		if (c[r].x < c[l].x) {
			e[h] = c[r];
			h++;
			r++;
		}
		else {
			e[h] = c[l];
			h++;
			l++;
		}
	}
	while (r <= mid) {
		e[h]= c[r];
		h++;
		r++;
	}
	while (l <= j) {
		e[h] = c[l];
		h++;
		l++;
	}
	h = i;
	while (h <= j) {
		c[h] = e[h];
		h++;
	}

}
int main(){
	scanf("%d", &f);
	bulid(1, 1, 20000);
	while (f--) {
		scanf("%d", &n);
		
		for(int i=1;i<=n;i++){
			scanf("%d %d", &c[i].x, &c[n+i].x);
			c[i].i = i, c[i].v = true;
			c[i + n].i = i; c[i+n].v = false;
		}//记录,方便后序离散化
		guibing(1, 2 * n);
		int j = 1;
		for (int i = 1; i <= 2 * n; i++) {
			if (c[i].x != c[j].x)
				j=i;//使相同的数离散化后相同
			if (c[i].v == true)
				d[c[i].i].x = j;
			else
				d[c[i].i].y = j;
		}
		//区间修改
		for (int i = 1; i <= n; i++) {
			tianjia(1, d[i].x, d[i].y, i);
		}
		//查找记录
		int q = 0;
		chazhao(1, q);
		printf("%d\n", q);
		//清除标记
		memset(b, false, (n+1)*sizeof(bool));
	}
    return 0;
}


http://www.kler.cn/a/589378.html

相关文章:

  • L2-3 花非花,雾非雾
  • maven使用install将jar包编译到本地仓库管理
  • 【系统架构设计师】操作系统 - 文件管理 ② ( 位示图 | 空闲区域 管理 | 位号 | 字号 )
  • 牛客周赛 Round 85
  • ElementUI 表格中插入图片缩略图,鼠标悬停显示大图
  • 电脑型号与尺寸
  • Leetcode Hot 100 200.岛屿数量
  • 【Agent】OpenManus-Flow-BaseFlow详细分析
  • element-ui progress 组件源码分享
  • 蓝牙技术联盟中国实体成立!华为、小米发声支持本土化战略
  • 实战ansible-playbook
  • 《C#上位机开发从门外到门内》3-3:基于USB的设备管理系统
  • MCP 开放协议
  • Visual Studio里的“公共语言运行时支持”各选项的作用是什么,分别适用于哪些场景?
  • 基于CPLD+MCU的3U机箱数字量输入采集板DI,主要针对标准DC110V开关量信号进行采集处理
  • LINUX驱动学习之IIC驱动-----以AP3216C为例
  • ZED X系列双目3D相机的耐用性与创新设计解析
  • 基于python+django+vue.js开发的停车管理系统运行-期末作业
  • 基于Python的tkinter开发的一个工具,解析图片文件名并将数据自动化导出为Excel文件
  • Spring 原生启动过程