B3917 [语言月赛 202401] 小跳蛙

OK 挠~ stop here~

好啊,现在呢,把手头的事情先放一放啊,我们来做道练习 OK?

好啊来:

小跳蛙

题目描述

有 ????−1 只小跳蛙在池塘中,依次被编号为 1,2,⋯ ,????−1。池塘里有 ???? 个位置,每一个位置上有一个数字 ???????? 。如果 ????????=0,则表示这个位置是一个空位;否则表示这个位置上存在一个编号为 ????????​ 的小跳蛙。

接下来的 ????−1 分钟,小跳蛙们将进行跳跃。第 ???? 分钟,编号为 ???? 的小跳蛙将跳到空位上。

请你输出 ????−1 分钟后池塘中每个位置的数字,即每个位置是否为空、小跳蛙编号是多少。

输入格式

输入共两行。

第一行一个整数 ????。
第二行 ????n 个整数 ????1,????2,⋯ ,????????​。

输出格式

输出一行 ????n 个整数 ????1,????2,⋯ ,????????​。 表示 n−1 分钟后池塘的状态。

输入输出样例

输入 #1

5
1 2 0 3 4

输出 #1

2 3 1 4 0

OK,我们的题目在黑板上也写完了

现在找个同学上黑板回答一下问题啊:

来,哪个坐在电脑边的同学;

啧啧啧,这都不会,我上课怎么讲的,坐,其他同学仔细听仔细看啊【吹小蜜蜂】

解题思路

这道题呢我们要知道,比如第一分钟,第一只小青蛙1需要跳到现在0的位置上;第二分钟,第二只小青蛙需要调到现在0的位置上;以此类推,直到第n-1分钟现在“池塘”里的小青蛙的位置。

现在我们把它分为两种思路:

思路1

梳理清思路后,我们现在需要知道两个点:

输入

首先是输入,题目中说输入两行,第一行输入位置数量,第二行输入详情;

我们可以得到:


int a[1000005]//此处要定义成全局变量,其余设立在主函数里
int  n;
cin>>n;
for(i=1;i<=n;i++)
{
	cin>>a[i];
}

关于位置的判断:

这里因为运行时间的原因,我选择再设置一个数组w,将其设1000005,并放置在全局变量里:

这个w数组只用来存储青蛙和空位的位置的

所以我们要在输入的时候将其存下;


int a[1000005],w[1000005]
int  n;
cin>>n;
for(i=1;i<=n;i++)
{
	cin>>a[i];
    w[a[i]]==i
}

然后题目中说让小青蛙n跳到现在的空位上,所以现在我们要让现在的小青蛙与现在的空位交换位置,

在此之前,

我们先要知道

现在的小青蛙的位置和当前空位的位置;

让现在的小青蛙与现在的空位交换位置

由此可以得出:


	for(i=1;i<n;i++)
	{
		wi=w[i];
		w0=w[0];
		t=a[wi];
		a[wi]=a[w0];
		a[w0]=t;
		t=w[i];
		w[i]=w[0];
		w[0]=t;
	}

题目上说N-1!!!!!

在数值上调完后记得也要在位置上变动!!!

输出


	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}

OK;

综上所述

总体来看就是这样的::

#include<iostream>
using namespace std;
int a[1000005],w[1000005];
int main()
{
	int  n,i,j,wi,w0;
	int t;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		w[a[i]]=i;
	}
	for(i=1;i<n;i++)
	{
		wi=w[i];
		w0=w[0];
		t=a[wi];
		a[wi]=a[w0];
		a[w0]=t;
		t=w[i];
		w[i]=w[0];
		w[0]=t;
	}
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	return 0;
}

思路2

规律

我们看样例输入和输出;

1 2 0 3 4;

2 3 1 4 0;

从上向下看,除了最高位以外,是不是每一位上都加了一?

然后最高的那一位的数字也就是n-1;

那么我们就可以得到一个思路:

核心

//

如果当前这个数是N-1的话,那么把这个数覆为0;

否则把这个数加一

//

翻译为c++语言就是:


if(a[i]==n-1)
{
	cout<<0<<" ";
}
else
{
	cout<<a[i]+1<<" ";
}

然后就是正经的输入输出:

综上所述

总体来看就是这样的:

#include<iostream>
using namespace std;
int a[1000005];
int main()
{
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<=n;i++)
	{
		if(a[i]==n-1)
		{
			cout<<0<<" ";
		}
		else
		{
			cout<<a[i]+1<<" ";
		}
	}
}

上一篇:Mac上配置多版本JDK


下一篇:lvs集群