思维--nkoj3653七的倍数

七的倍数

Description

农夫约翰的N头奶牛排成一排，每头奶牛都有约翰制定的奶牛编号。约翰想要拍一张奶牛的照片，他希望该照片满足下列两个要求： 
1.照片中奶牛的数量尽可能多； 
2.照片中奶牛的编号之和为7的倍数； 

请你帮组约翰计算，满足条件的照片中，奶牛的数量最多是多少

Input

第一行，一个整数N表示奶牛的数量 (1≤N≤50,000) 
接下来N行，每行一个整数，依次给出了眉头奶牛的编号，编号的范围[0…1,000,000]。

Output

一行，一个整数，表示奶牛最多的照片中奶牛的数量，如果无解，输出0

Sample Input

7
3
5
1
6
2
14
10

Sample Output

5

Hint

5+1+6+2+14 = 28

分析：

sum[i]表示前i个数模7之后的前缀和。显然，若sum[i]==sum[j]则i到j这一段满足要求。

l[i]表示sum中i最先出现的位置；r[i]表示sum中i最后出现的位置。

所求的就是 r[i]-l[i]的最大值

#include<iostream>
#include<cstdio>
using namespace std;
int a[50005],sum[50005],l[7],r[7];
int main(){
	int n,i,j,k,ans=0;
	cin>>n;
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(i=1;i<=n;i++){
		sum[i]=(sum[i-1]+a[i])%7;
	}
	for(i=1;i<=n;i++){
		if(l[sum[i]]==0)l[sum[i]]=i;
	}
	for(i=n;i>=1;i--){
		if(r[sum[i]]==0)r[sum[i]]=i;
	}
	for(i=0;i<7;i++){
		ans=max(ans,r[i]-l[i]);
	}
	cout<<ans;
}

最后

以上就是简单香菇为你收集整理的思维--nkoj3653七的倍数的全部内容，希望文章能够帮你解决思维--nkoj3653七的倍数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。