题目大意
给你N个正数的序列,从中找到连续的若干数,使得其和刚好是N的倍数。
解题思路:
典型的鸽巢原理。
$Sum[i]$为序列中前$i$项的和。则有两种可能:
1.若有$Sum[i]$是$N$的倍数,则直接输出前$i$项。(最好的结果)
2.如果没有任何的$Sum[i]$是$N$的倍数,则计算Result = Sum[i] % N。根据鸽巢原理,肯
定有Sum[i]%N==Sum[j]%N并且$i != j$。则第 j 到第 i 项数的和即为N的倍数。
前缀和
预处理一个前缀和数组,把算法优化到线性
前缀和Sum[i]定义为序列中从第1个数到第i个数的和。利用前缀和可以快速计算任意一个子序列的和。例如,要计算第j+1个到第i个数的和,可以用Sum[i] - Sum[j]来计算。
下面例子中第2到第4个的和就是Sum[4] - Sum[1] = 12 = 3+4+6
arr = [0, 3, 4, 6, 2, 5]
Sum = [0, 3, 7, 13, 15,20]
鸽巢原理解题
想象一下,如果我们有N+1个物品放到N个抽屉里,那至少有一个抽屉里至少有两个物品。同理,如果有超过N个的前缀和模N的结果,那么至少有两个是相同的。这就是为什么我们可以确定存在两个相同模值的前缀和。
这个算法只需要遍历一次序列来计算所有的前缀和并取模,时间复杂度为O(N)。可以在O(1)时间内检查或更新模值。
核心思路
这里的关键在于理解前缀和的差值代表的是什么。假设我们有两个前缀和Sum[i]和Sum[j],并且i > j。如果这两个前缀和对N取模的结果相同,即:
Sum[i] mod 𝑁=Sum[j] mod 𝑁
Sum[i] mod 𝑁=Sum[j] mod 𝑁
这个等式可以重写为:
Sum[i]−Sum[j]=𝑘×𝑁
Sum[i]−Sum[j]=𝑘×𝑁
这里的𝑘是某个整数。这个等式说明什么呢?它告诉我们,从序列中第j+1个元素到第i个元素的子序列和正好是N的倍数。
代码实现
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int Sum[10010],A[10010];
int main()
{
int N;
while(~scanf("%d",&N))
{
memset(Sum,0,sizeof(Sum));
for(int i = 1; i <= N; ++i)
{
scanf("%d",&A[i]);
Sum[i] = (Sum[i-1] + A[i]) % N;
}
int Flag = 0;
for(int i = 1; i <= N; ++i)
{
if(Sum[i] % N == 0)
{
printf("%d\n",i);
for(int j = 1; j <= i; ++j)
printf("%d\n",A[j]);
Flag = 1;
}
else
{/*
这里运用到了抽屉原理(鸽巢原理)。
如果我们有N+1个物品放到N个抽屉里,那至少有一个抽屉里至少有两个物品。
如果有超过N个的前缀和模N的结果,那么至少有两个是相同的。这就是为什么我们可以确定存在两个相同模值的前缀和。
[1,2,3,4,1]
[]
*/
for(int j = 1; j < i; ++j)
{
if(Sum[i] == Sum[j])
{
printf("%d\n",i-j);
for(int k = j+1; k <= i; ++k)
printf("%d\n",A[k]);
Flag = 1;
break;
}
}
}
if(Flag)
break;
}
}
return 0;
}
Java 版本
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args)throws Exception {
// TODO Auto-generated method stub
int n = Integer.parseInt(in.readLine());
int[]pre=new int[10010];
int[]arr = new int[10010];
// System.out.println(n);
for (int i=1;i<=n;++i) {//读入数据并创建前缀和数组
arr[i]=Integer.parseInt(in.readLine());
pre[i] = (pre[i-1] + arr[i])%n; //爆int
}
int flag = 0;//创建哨兵
for(int i=1;i<=n;++i) {
//如果前缀和满足倍数关系则输出;
if(pre[i]%n==0) {
System.out.printf("%d\n",i);//输出打印数字数量
for(int j = 1; j <= i; ++j)
System.out.printf("%d\n",arr[j]);
flag = 1; //改变哨兵状态
}else {
for(int j=1;j<i;++j) {
if(pre[i]==pre[j]) {
System.out.printf("%d\n",i-j);
for(int k=j+1;k<=i;++k) {
System.out.printf("%d\n",arr[k]);
}
flag = 1;
break;
}
}
}
if(flag==1) {
break;
}
}
}
}