Educational Codeforces Round 161 (Rated for Div. 2) D题 一排人有左右关系,并且会剔除部分人

发布时间:2024年01月21日

Problem - D - Codeforces

这道题我想到数组里删除难处理了,链表好删,但竟然没想到用数组模拟链表哇。

其实后来做的时候还是遇见了问题。这种一排人删除个别人的题做的少,这次记住方法和关系,以后无脑提速写了。

目录

题意:

思路:

(可以直接看代码很好懂很精妙):

核心代码:


题意:

一排怪兽,每个怪兽会打自己左右的,也分别有个防御值。受到的伤害大于防御值就寄了,剩余的接着组成一排接着打。

思路:

首先自己左右没换的,就不需要重复算了。

然后难处理的是左右关系,寄了的左右需要处理(比如a b c ,b寄了)。左边a的右就是我们寄了的b,现在接到寄了b的右c。

寄了b的右边c同理,c其左接寄了b的左边a。

为什么说难处理,因为寄了的右边也就是这里的c可能也寄了,不过你可以发现,对他做相同的处理是不会出问题的(比如a b c d,删b后删c,a和d还是正常接的,直接去看代码吧)。这里用个set会非常方便。

—————

(可以直接看代码很好懂很精妙):

(由题知要弄n轮即这里time)

dead是死亡数组,我们处理它的每个元素的左右。(开始需预处理暴力算一轮)

1.我们只需调整被删aim的 左元素的右 和 右元素的左。而且这样调整连续删除也不会出问题。(自己模拟一下就能发现)

2.我们把 aim 的左右直接放进一个set里(这里的newattack),同时删去set中的aim自己

根据set的特性,两个元素的左就算相同也只会进一个。

而删除自己,就避免了已删元素的重复计算(只有连续删除挨着元素才会进入被删元素)

while (time--)
	{
		cout << dead.size() << " ";
		set<int>newattack;
		while (dead.size())//处理已死的左右
		{
            //1
			int aim = dead.front();
			right[left[aim]] = right[aim];
			left[right[aim]] = left[aim];//n+1会被牵扯了

            //2
			newattack.insert(left[aim]);
			newattack.insert(right[aim]);
			newattack.erase(aim);
			dead.pop();
		}
		for (auto i : newattack)//计算左右改变了的元素
		{
			if (i != 0 && i != n + 1)
				if (attack[left[i]] + attack[right[i]] - defense[i] > 0)
				{
					dead.push(i);
				}
		}
	}
	cout << dead.size();
	cout << endl;

核心代码:

#define ll long long
#define endl "\n"
const ll inf = 1e9;


void solve()
{
	int n; cin >> n;
	vector<int>attack(n + 2), defense(n + 2), left(n + 2), right(n + 2);
	for (int i = 1; i <= n; i++)
	{
		cin >> attack[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> defense[i];
	}
	for (int i = 1; i <= n; i++)
	{
		left[i] = i - 1;
		right[i] = i + 1;
	}
	left[n + 1] = 0;
	right[0] = n + 1;
	queue<int>dead;
	for (int i = 1; i <= n; i++)
	{
		if (attack[i - 1] + attack[i + 1] - defense[i] > 0)
		{
			dead.push(i);
		}
	}
	int time = n - 1;
	while (time--)
	{
		cout << dead.size() << " ";
		set<int>newattack;
		while (dead.size())
		{
			int aim = dead.front();
			right[left[aim]] = right[aim];
			left[right[aim]] = left[aim];//n+1会被牵扯了

			newattack.insert(left[aim]);
			newattack.insert(right[aim]);
			newattack.erase(aim);
			dead.pop();
		}
		for (auto i : newattack)
		{
			if (i != 0 && i != n + 1)
				if (attack[left[i]] + attack[right[i]] - defense[i] > 0)
				{
					dead.push(i);
				}
		}
	}
	cout << dead.size();
	cout << endl;
}

文章来源:https://blog.csdn.net/JK01WYX/article/details/135726028
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。