AcWing 1987.粉刷栅栏（离散化，差分）

题目链接

https://www.acwing.com/problem/content/1989/

思路

差分，但是数据范围很大，需要开map进行处理。

AC代码

#include 
#include 
#include 
#include 
using namespace std;
int n;
mapb;
int main(int argc, char* argv[])
{
	cin >> n;
	int x = 0;//记录当前位置
	while (n--)
	{
		int t;
		char s;
		cin >> t >> s;
		if(s=='R')
		{
			b[x]++;
			b[x + t]--;
			x += t;
		}
		else
		{
			b[x - t]++;
			b[x]--;
			x -= t;
		}
	}
	int res = 0;
	int sum = 0;
	int last;
	for(auto& [i,j]: b)
	{
		if (sum >= 2)//被粉刷的总数大于等于2层
			res += i - last;//答案加上现在这一层减上一层的数量
		sum += j;//加上被标记的这一结点的数量
		last = i;//记录遍历过的这个结点
	}
	cout << res;
}

心得

不太懂离散化是啥诶。。

算法题

相关

腾讯二面算法题：朋友圈问题

从今天开始刷算法题-2021.12.03

算法题（十）

算法题：27移除元素

leetcode常规算法题复盘（基础篇）——线性表java实现

算法题整理

面试常考算法题之二叉树的先序遍历

牛客网高频算法题系列-BM13-判断一个链表是否为回文结构

牛客网高频算法题系列-BM15-删除有序链表中重复的元素-I

二分算法题1

Java自定义加密字符串算法题目

标签