c++ - 超过 spoj CANDYSTN 的时间限制

Question

  #include <iostream>
    using namespace std;
    int main()
    {
        long long int i,a,b,arr[10000]={0},dif,sum=0,tem=1,t;
        cin>>t;
        for(int m=0;m<t;m++)
        {
            cin>>a>>b;
            for(i=0;i<b;i++)
            {
                cin>>arr[i];
            }
            for(i=0;i<(b-1);i++)
            {
                dif=arr[i+1]-arr[i];
                sum=sum+dif;
                if(sum<=0 && tem>sum)
                {
                    tem=sum;
                }

            }
            if(a>(1-(tem)))
                cout<<1-tem<<"\n";
            else
                cout<<"-1"<<"\n";

        }
            return 0;
    }

https://ideone.com/vi7TVl 这是我的代码的链接。我无法实现动态编程。

请帮忙。我能做些什么来减少我的时间。

Answer 1

这个问题需要读取大量数据，所以cin速度太慢了。你可以scanf改用。

Answer 2

删除阵列，它不需要。

使用两个变量，present和previous。present变量包含读入的值。变量previous包含先前输入的值。

您可以消除 2 个循环。

  cin >> a >> b;
  int previous = 0;
  int present = 0;
  cin >> present;
  for (unsigned int i = 0; i < b - 1; ++i)
  {
    previous = present;
    cin >> present;
    dif = present - previous;
    sum += diff;
    if ( (sum < 0) && (tem > sum))
    {
      tem = sum;
    }
  }

顺便说一句，变量名的长度可以超过 3 个字母。