【NOIP普及组】模拟考试(10.29)——海港的船只

时间:2024-02-17 19:50:34

问题 A: 海港的船只(ship.cpp)

时间限制: 1 Sec  内存限制: 128 MB

题目描述

Mirko 生活在一个小镇上,这个小镇上有一个海港,很少有船只过来停靠。很难得的,有一天所有的船只都来到了这个海港。Mirko记下了这个日子,把它列为第一天.从那以后,只要有船来到这个港口,(假设不会再有新的船)Mirko都会记下这个日子。Mirko发现所有的船来到这个港口都是周期性的。比如某艘船的周期为3,则它来到这个港口的日子分别为1,4,7,10等等。

给出Mirko记录的日子的一个列表(包含今天,当然今天也有船只过来),计算出最少有多少只船来到这个港口。

输入

第一行包含一个整数N(2<=N<=5000),记录的天数。

接下来的N行包含N个数,表示记录的N个日子。这N个数是升序排列的。第一个数表示Mirko开始记录的第一天,最后一个数表示今天。第一个数总是1,最后一个数(今天)小于1000000000

输出

 第一行也是唯一的一行,输出最小的船只数。

样例输入

3
1
3
4

样例输出

2

提示

样例解释:记录了三个日子,分别是第1天,第3天,第4天,所以最少有2条船来到这个港口。一条周期为2,一条周期为3.


#------------------------------------------------------------------------------#

这题完全就是水的……
很简单,从第二个开始(因为第一天所有的船都到了),只要后面的是它(a[i])的倍数(包括自己)就删掉,这样每重复一次sum++,直到结束(i<=n)。可是……错了!!
why?

啊啊啊!查的时候要是a[i]-1!!因为是从1开始的!!假如说a[i]=2,则3,4,5,6……均可以删

就这一点,害得我……香菇

代码:
#include<cstdio>
int a[50005];
int n,sum;
void s(int i)//删掉第i个数
{
	for(int k=i;k<=n;k++)
		a[k]=a[k+1];
	n--;//注意长度一定要--,因为删了一个数
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=2;i<=n;i++)
	{
		int q=a[i]-1;
		s(i--);//注意下标要--,注意不要--i,因为要先处理,下标再返回。原因同n--
		sum++;//总个数++
		for(int j=i+1;j<=n;j++)
			if((a[j]-1)%q==0)//是它的倍数(就差了这里和前面的--啊啊啊,一定不要忘了)
				s(j--);//删掉此数
	}
	printf("%d\n",sum);
}

                                                                                                                                       By WZY