「ALFR Round 3」B Swap & Delete

有人看到这道题可能直接就懵逼了，但是说句实话，如果你看懂了样例你就会发现，这题它纯纯一个分类讨论啊！！！

根据样例，我们可以发现，一旦

a_i

与

a_1

或者

a_n

相等，这组数据就只要两个操作：

如果 $a_n\ne a_i$ ，那就交换 $a_n$ 和 $a_i$ ，否则交换 $a_1$ 和 $a_i$ 。
直接给整个序列删掉！（因为上一步已经使得 $a_1=a_n$ 了）

但是，先别急着打！看数据：

数据范围

子任务分值限制
$1$ $10$ $n\le 3$
$2$ $20$ $n\le 10$
$3$ $20$ $a_i\le 2$
$4$ $10$ 保证所有 $a_i$ 相等
$5$ $40$ -

对于 $100\%$ 的数据， $1\le T \le 5$ ， $1\le n\le 10^5$ ， $0\le a_i\le 10^9$ 。

子任务	分值	限制
$1$	$10$	$n\le 3$
$2$	$20$	$n\le 10$
$3$	$20$	$a_i\le 2$
$4$	$10$	保证所有 $a_i$ 相等
$5$	$40$	-

子任务

4

，保证所有

a_i

都相等？！

于是，我们可以轻松地得到另一个东西：如果

a_1

本来就等于

a_n

，你就可以直接给整个序列删掉！

那为什么不能先判样例的情况再判上面那种情况呢？

先给大家造一组~~有毒的~~数据：

CPP

1 2 1 2 1

如果你要是先判样例的情况的话。。。~~你懂的hhh，虽然我没试探过这道题目的数据强度，但是你自己去可以试试。~~

然后我们还可以把上面那组数据爆改一下：

CPP

3 2 1 2 4

于是，我们得到下面的结论：

如果

a_i=a_j

，我们就可以发现，我们需要

3

次操作就可以把整个序列删掉，be like：

CPP

第一步：2 3 1 2 4
第二步：2 3 1 4 2
第三步：（只有空气了，因为序列被删光了（））

但是，但是，这样了还没结束！

因为，如果这

n

个数字互不相等，怎么弄？

呃，可想而知，我们要。。。一个一个删。。。于是，这种情况就要

n

次操作了。

综上，所有情况都被推导出来了。

然后就是，上代码！！！

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int A=1000000005;
int n,a[N];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		if(a[1]==a[n])
		{
			cout<<1<<endl;//先判有没有 a[1]==a[n] 这种情况，避免发生类似 1 2 1 2 1 的数据把你卡了。
		}
		else
		{
			bool flag=1;
			for(int i=2;i<n;i++)
			{
				if(a[i]==a[1]||a[i]==a[n])
				{
					cout<<2<<endl;
					flag=0;
					break;
				}
			}//判样例的情况。
			if(flag)
			{
				bool flag2=1;
				for(int i=2;i<n;i++)
				{
					for(int j=i+1;j<n;j++)
					{
						if(a[i]==a[j])
						{
							cout<<3<<endl;
							flag2=0;
							break;
						}
					}
				}//再判上面的第三种情况。
				if(flag2)
				{
					cout<<n<<endl;
				}//如果都不满足，那就是剩下的那种情况，输出 n 就完了！
			}
		}
	}
	return 0;//完结撒花~~~
}

「ALFR Round 3」B Swap & Delete

文章操作

数据范围

相关推荐

评论

「ALFR Round 3」B Swap & Delete