c++ - 如何修复 STAMPS 挑战中的 SPOJ 时间限制超出错误？

Question

这是问题的链接:http://www.spoj.com/problems/STAMPS/ ;这是当前代码的 ideone 链接:http://ideone.com/AcHfc6 ;这是代码:

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() 
{
    int t,x,n,sum,sum2,count,i,j;
    scanf("%d",&t);
    for(j=1;j<=t;j++)
    {
        cin>>x>>n;
        sum=0;
        int offer[n];
        for(i=0;i<n;i++)
        {
            cin>>offer[i];
            sum+=offer[i];
            sort(offer,offer+n);
        }

        if(sum>=x)
        {
            sum2=0;
            count=0;
            for(i=n-1;i>=0;i--)
            {
                sum2+=offer[i];
                if(sum2<=x)
                    count++;
                else
                    break;
            }
            cout<<"Scenario #"<<j<<":"<<endl;
            cout<<count<<endl;
            cout<<endl;
        }
        else
        {
            cout<<"Scenario #"<<j<<":"<<endl;
            cout<<"impossible"<<endl;
            cout<<endl;
        }
    }
    return 0;
}

代码给出了给定测试用例的正确答案，但它会导致 TLE。我已经尝试将我的 cin 和 cout 转换为 scanf/printf 但是，奇怪的是，答案不一样，我不知道答案之间有何不同。

出了什么问题？

Answer 1

我怀疑你的主要问题在这里:

for(i=0;i<n;i++)
{
    cin>>offer[i];
    sum+=offer[i];
    sort(offer,offer+n);
}

您对输入的每个数字的数据进行排序。此外，您对随机数据进行排序，因为数组中只有 i 行有效数据，而不是 n 行。排序应该在循环外完成一次:

for(i=0;i<n;i++)
{
    cin>>offer[i];
    sum+=offer[i];
}
sort(offer,offer+n);