【例题 6-5 UVA 12657 】Boxes in a Line

在这里输入题意

【题解】

双向链表模拟题。
移动的时候,要注意它就在所需要的位置的情况。那种情况不移动。
(如果已经在所需位置了,还用链表的插入方式强行移动的话,会WA到死..)

【代码】

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e5;

int n, m,flag;

pair <int, int> v[N+10];

void cr(int x0,int y0,int z0,int x,int z) //x0,y0,z0  x_z 把y0插入到_位置

{

	v[x0].second = z0;v[z0].first = x0;

	v[x].second = y0; v[z].first = y0;

	v[y0].first = x, v[y0].second = z;

}

int main()

{

	/*freopen("F:\\rush.txt", "r", stdin);

	freopen("F:\\rush_out.txt", "w", stdout);*/

	int kase = 0;

	while (~scanf("%d%d", &n, &m))

	{

		v[0].second = 1;

		for (int i = 1; i <= n; i++)

			v[i].first = i - 1, v[i].second = i + 1;

		v[n + 1].first = n;

		flag = 0;

		printf("Case %d: ", ++kase);

		for (int i = 1; i <= m; i++)

		{

			int ope,x,y;

			scanf("%d", &ope);

			if (flag && ope <= 2) ope = 3 - ope;

			switch (ope)

			{

				case 4:

				{

					flag = !flag;

					break;

				}

				case 1:

				{

					scanf("%d%d", &x,&y);//x移动到y的左边

					if (x == v[y].first) break;

					cr(v[x].first, x, v[x].second, v[y].first, y);

					break;

				}

				case 2:

				{

					scanf("%d%d", &x, &y);//x移动到y的右边

					if (x == v[y].second) break;

					cr(v[x].first, x, v[x].second, y, v[y].second);

					break;

				}

				case 3:

				{

					scanf("%d%d", &x, &y);

					int temp;

					if (v[y].second != x)//y_x || xy

					{

						//记录x的左边是什么temp

						//把x插入到y的右边

						//在把y插入到temp的右边

						temp = v[x].first;

						cr(v[x].first, x, v[x].second, y, v[y].second);

						if (y!=v[temp].second)cr(v[y].first, y, v[y].second, temp, v[temp].second);

					}

					else //yx

					{

						//把y插入到x的右边

						temp = v[x].second;

						cr(v[y].first, y, v[y].second, x, v[x].second);

					}

					break;

				}

				default:

					break;

			}

		}

		ll ans = 0, cnt = 0;

		if (!flag)

			for (int i = v[0].second;i != n + 1; i = v[i].second)

			{

				cnt++;

				if (cnt & 1) ans += i;

			}

		else

			for (int i = v[n+1].first; i != 0; i = v[i].first)

			{

				cnt++;

				if (cnt & 1) ans += i;

			}

		printf("%lld\n", ans);

	}

	return 0;

}

巴特西

【例题 6-5 UVA 12657 】Boxes in a Line

最新文章

热门文章