题意 给你一个长度为的序列,问这个序列中最长的不能被整除的子段的长度是多少。 题解 首先整个序列的和不能被整除那答案就是,那么接下来考虑我们可以使用双指针来扫一遍。这是根据一个点来实现的,就是几个数的和若能被整除,那么删去一个不能被整除的数,那么和也不能被整除,使用我们在遇到第一个不能被整除的点时候就可以跳出了。 复杂度 时间复杂度##代码 #include <iostream>using namespace std;const int N=1e5+5;int a[N];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n,k;        int flag=0;        scanf("%d%d",&n,&k);        long long sum=0,m;        for(int i = 0; i < n; i++)        {            scanf("%d",&a[i]);            sum+=a[i];        }        m=sum;        if(sum%k)        {            printf("%d\n",n);            continue;        }        for(int i=n-1,j=0;i>=j;i--,j++)        {            if((m-a[i])%k)            {                printf("%d\n",n-j-1);                flag=1;                break;            }            else            {                m-=a[i];            }            if((sum-a[j])%k)            {                printf("%d\n",n-j-1);                flag=1;                break;            }            sum-=a[j];        }        if(!flag)        {            printf("-1\n");        }    }    return 0;}
点赞 0
评论 0
全部评论

相关推荐

07-25 10:17
仰恩大学 营销
bg双非,被挂了
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
07-30 13:50
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务