【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


相关文章