chenxie95 / SJTU_C-_Cource

上交2022小学期 程序设计思想 答疑论坛
1 stars 0 forks source link

数组23关小球碰撞 #7

Open paean4h opened 2 years ago

paean4h commented 2 years ago

和上面那位运行超时的同学类似,在自己电脑上迅速运行,但在ice上从第一组便开始显示超时,源代码如下:

#include <iostream>
using namespace std;

int main()
{
    int a,v0=1,t=0,l,start=0,end,fast,slow,tmp,j,tmp2;
    bool m=true;
    cin>>a>>l;
    const int n=a;
    int r[n+1]={},v[n+1]={},aa[n]={};
    for(int i=0;i<n;i++)
    cin>>aa[i];
    r[0]=aa[0];v[0]=v0;v0 *=-1;

    for(int i=1;i<n;i++)
    {
        a=aa[i];
        j=0;
        if(r[i-1]<a) {r[i]=a;tmp2=v[i]=v0;}
        else
        {
            tmp2=v0;
            while(j<i)
            {
                if(a<r[j]) 
                {
                    tmp=r[j];r[j]=a;a=tmp;tmp=v[j];v[j]=v0;v0=tmp;
                    for(int k=j;k<i;k++){tmp=r[k+1];r[k+1]=a;a=tmp;tmp=v[k+1];v[k+1]=v0;v0=tmp;}
                    break;
                }
                j++;
            }
        }
        v0 =tmp2*(-1);
    }

    fast=l-r[n/2];end=n-1;r[n]=l+3;
    if(r[start]==0&&r[end]==l&&v[start]==-1&&v[end]==1&&n==2) {fast=slow=0;m=false;}
    while(m)
    {
        t+=1;
        for(int i=start;i<=end;i++)
        {
            a=r[i]+v[i];v0=r[i+1]+v[i+1];
            if(a<v0) r[i] +=v[i];
            if(a==v0) {r[i] +=v[i];r[i+1] +=v[i+1];v[i] *=-1;v[i+1] *=-1;i++;}
            if(a>v0) {v[i] *=-1;v[i+1] *=-1;i++;}
        }
        if(r[start]<=0) {r[start] -=2;start +=1;fast=(fast<t)?fast:t;}
        if(r[end]>=l) {r[end] +=2;end -=1;fast=(fast<t)?fast:t;}
        if(start==end) {m=false;slow=t+((v[end]>0)?(l-r[end]):r[end]);break;}
        if(start>end) {slow=t;m=false;break;}
        if(t>100000){slow=t+((v[end]>0)?(l-r[end]):r[end]); cout<<"???";break;}
    }
    //每一秒进行迭代直到最后一个球超出范围
    cout<<fast<<" "<<slow;
    return 0;
}

添加了t>10000的条件后发现在ice上可以正常运行且前9组测试集均可通过,但第10组仍无法通过,且可见的两组测试结果并未输出t>10000触发后应该输出的??? 若无t>10000的终止条件在自己电脑上的vs上尝试输入许多不同数据均未发现错误,但在ice上从第一组测试便是死循环,我百思不得其解

SkyTbac commented 2 years ago

参考https://github.com/chenxie95/SJTU_C-_Cource/issues/5中回答的方法