速通ACM省铜第十七天赋源码（Racing）

原创于 2025-09-28 15:02:28 发布 · 1k 阅读

21 ·

CC 4.0 BY-SA版权

文章标签：

#算法 #c++

算法同时被 2 个专栏收录

18 篇文章

订阅专栏

ACM

17 篇文章

订阅专栏

引言：

感觉相比起比赛，还是刷CF的题的强度高一点，昨天比赛我开了三题，但真用到点脑子的只有第三题，前俩题并没有对自己实力的感觉，只有打出第三题的时候有了些许成就感，本来今天是想着补一下那场的第四题的，因为有佬教了我思路，可我对用 stl 并不熟练，如果直接开数组又会超内存，所以就没有补了,但大致思路很简单，就是用bfs即可，因为每个点只会访问一次，我这里题一嘴就带过啦

接下来，我们来讲一下今天要讲的题，这题确实有意思，他是CF里评级评为1400的一道题，但打出来还是挺有成就感的

那么接下来，就进入今天的题目讲解啦————————>

Racing

按照惯例，我们先来看题目

题意分析

题目链接在这里Problem - 2110C - Codeforces

不想跳转的可看下图

这题，先不要想成题目说的左右，把他想成上下好理解点

这题的意思很简单，就是先告诉你有几个障碍，然后再输入一个数组，这个数组不同下标上的元素代表对应不同障碍物的运动方式，1代表上升1格，0代表平飞，-1代表可以上升1格或者平飞由你决定

然后题目会告诉你每个障碍的下限和上限高度，只要在这个范围内，就不会撞到障碍了

然后题目问我们是否存在一串指令可以让这个机子不碰到障碍经过所有障碍

如果存在就输出每次的指令

如果不存在就输出-1

那么，这题的题目意思就讲解完啦，接下来我们来看这题的逻辑梳理

逻辑梳理

这题其实只要思路对了，就很简单了，我们先来想一想这个机子的俩种情况

指令只有－１，０和１，－１只能代表０或者１，具体是什么就得看我们给他赋的值了

那么看了指令，我们很清楚，这个机子是不会往下降的，只会上升或者平着飞，那么我们接着分析

首先这个机子一开始的时候是在０高度的，相当于在地上，然后在到第一个障碍前，这个机子会先执行指令，

如果这个指令是０，那他的高度就不会变

如果指令是１，那么他就要上升１

如果是－１，因为是用户决定给他指令，所以我们先把－１存在一个队列里，具体是什么指令我们根据情况给

那么我们就分情况来讨论

首先我们可以先给定一个变量来定为在到某个障碍物前肯定会到的一个高度（即最低高度）

如果这个最低高度低于下一个障碍物的下限时

我们就可以动用存在队列里的－１的那些指令了，把－１变成１，然后最低高度加一，直到达到下一个障碍物的下限就可以了，如果所以－１指令都用完了，还是到不了下一个障碍物的下限的时候，我们就直接输出－１就可以了

那么说完低于下限，我们来想想上限，如果最低高度高于下一个障碍物的上限时，因为不能下降，所以直接输出－１即可

当然上限最明显想到的就是这个，但是还有一个隐含的细节，这个细节很关键：

就是还必须要满足　最低高度＋队列元素个数＜下一个建筑上限，如果不满足就出队元素，然后将那个位置的－１指令变成０，直到满足为止，若无法满足，就输出－１

因为这个操作可以保证之后将队列里元素变为１的时候不会让前面处理完的部分出现问题，这个可以好好想一想。其实上面那个式子也包含了最低高度高于下一个障碍物的上限的那种情况，所以只需要考虑这个式子就可以了

那么这么操作完，如果走完都符合条件，没有输出－１，那么我们就输出数组，但这个时候数组不一定－１全被用完了，这个时候只要把－１变成０就可以了，以防徒增变数，让他不确定的地方平飞就可以了

这题的逻辑挺简单的，就是不容易想我觉得，那么我们就进入代码的实现环节

代码实现

具体的需要注意的一些细节在逻辑梳理里已经讲完啦，那么这边就直接上ＡＣ码啦

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;

int t, n;
int a[200010];
int l[200010];
int r[200010];

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	int Low = 0;
	queue<int> temp;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == -1)
		{
			temp.push(i);
		}
		else
		{
			Low += a[i];
		}
		while (Low < l[i])
		{
			if (temp.empty())
			{
				cout << "-1" << endl;
				return;
			}
			a[temp.front()] = 1;
			Low++;
			temp.pop();
		}
		while (Low + temp.size() > r[i])
		{
			if (temp.empty())
			{
				cout << "-1" << endl;
				return;
			}
			a[temp.front()] = 0;
			temp.pop();
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cout << max(a[i], 0) << " ";
	}
	cout << endl;
}

int main()
{
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

那么，这题就讲解完毕啦