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

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;
}