1046 Shortest Distance测试点3超时

超时我一般想到先把输入输出改成scanf之类的,但是还是超时,不过肉眼可见循环用的多
超时的思想:求距离时用两个for循环正向和逆向求距离,比较大小

#include<iostream>
using namespace std;
int n,m[100010];
int distance(int a,int b)
{
    int sum1=0,sum2=0,t;
    for(int i=0;i<b-a;i++)
        sum1+=m[a+i];
    t=n-b+a;
    for(int i=0;i<t;i++)
    {
        if(a-i-1==0)
            a=n+i+1;
        sum2+=m[a-1-i];
    }
    if(sum1>sum2)
        return sum2;
    else
        return sum1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&m[i]);
    int k,q[10010][2],p[10010],temp;
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        scanf("%d %d",&q[i][0],&q[i][1]);
        if(q[i][0]>q[i][1])
        {
            temp=q[i][0];
            q[i][0]=q[i][1];
            q[i][1]=temp;
        }
        if(q[i][0]==q[i][1])
        {
            p[i]=0;
            continue;
        }
        p[i]=distance(q[i][0],q[i][1]);
    }
    for(int i=0;i<k;i++)
        printf("%d\n",p[i]);
    return 0;
}

改正后:逆向的距离只需要用圆周长➖正向距离,这样几乎可以节省一半的时间,然后就全部ac了

#include<iostream>
using namespace std;
int n,m[100010],sum=0;
int distance(int a,int b)
{
    int sum1=0,sum2=0,t;
    for(int i=0;i<b-a;i++)
        sum1+=m[a+i];
    t=n-b+a;
  /*  for(int i=0;i<t;i++)
    {
        if(a-i-1==0)
            a=n+i+1;
        sum2+=m[a-1-i];
    }*/
    if(sum1>sum-sum1)
        return sum-sum1;
    else
        return sum1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&m[i]);
        sum+=m[i];
    }
    int k,q[10010][2],p[10010],temp;
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        scanf("%d %d",&q[i][0],&q[i][1]);
        if(q[i][0]>q[i][1])
        {
            temp=q[i][0];
            q[i][0]=q[i][1];
            q[i][1]=temp;
        }
        if(q[i][0]==q[i][1])
        {
            p[i]=0;
            continue;
        }
        p[i]=distance(q[i][0],q[i][1]);
    }
    for(int i=0;i<k;i++)
        printf("%d\n",p[i]);
    return 0;
}
上一篇:python学习笔记——列表


下一篇:android 自定义Preference CheckBoxPreference ListPreference的用法