题意:
找到一个连续的区间,这个区间的和能够被k整除,
满足条件的最长的区间长度是多少
分析:
首先需要知道一件事,如果两个数a ,b 对 k 取模的余数是一样的
那么 a-b 一定是 k 的倍数。
基于此,我们可以维护一个给出数组的前缀和
遍历前缀和数组,依次对 k 取模,
如果余数m是 0 ,直接更新 ans,此时的长度一定是目前最长的
如果余数m不是 0, 就记录一下出现这个余数的坐标,
如果这个余数m之前已经被记录过,就 i-pos[m] ,
这个区间的和一定是 k 的倍数。
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
int a[MAXN];
LL sum[MAXN];
int pos[100];
int main()
{
int n, k, m, ans = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = a[i] + sum[i-1];
}
for (int i = 1; i <= n; i++)
{
m = sum[i] % k;
if (m == 0)
ans == m;
else
{
if (pos[m]==0)
pos[m] = i;
ans = max(ans, i-pos[m]);
}
}
cout << ans << endl;
return 0;
}
Comments | NOTHING