“食品订购”计划超过测试9的时限

Question

因此，我最近开始在CodeForces上工作，练习从旧的竞赛(甚至可能开始参加当前的比赛)，但有一个问题，我似乎无法使一个足够有效的程序，以通过所有的测试。这是我的代码：

#include 
using namespace std;
struct food
{
    long long stock, cost;
} v[100005];
struct sorted_food
{
    long long type, cost;
} s[100005];
bool compare (sorted_food lhs, sorted_food rhs)
{
    return (lhs.cost < rhs.cost && lhs.cost && rhs.cost);
}
int main()
{
    struct order
    {
        long type;
        long long dishes;
    } cust; ///cust = customer
    struct minim
    {
        long pos=0;
        long value=2147483647;
    } mn;
    long long i,n,m,cost,d,j,k=1;
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        cin >> v[i].stock;
    }
    for (i=1; i<=n; i++)
    {
        cin >> v[i].cost;
        s[k].cost = v[i].cost;
        s[k].type = i;
        k++;
        if (v[i].cost < mn.value && v[i].stock)
        {
            mn.value = v[i].cost;
            mn.pos = i;
        }
    }
    sort(s + 1, s + k, compare);
    for (i=1; i<=m; i++)
    {
        cost = 0;
        cin >> cust.type >> cust.dishes;
        d=v[cust.type].stock;
        v[cust.type].stock -= cust.dishes;
        if (v[cust.type].stock >= 0)
            cost = v[cust.type].cost * cust.dishes;
        else
        {
            cost = v[cust.type].cost * (cust.dishes + v[cust.type].stock);
            v[cust.type].stock = 0;
            cust.dishes -= d;
            while (cust.dishes)
            {
                if (cust.dishes > v[mn.pos].stock)
                {
                    cust.dishes = cust.dishes - v[mn.pos].stock;
                    cost += v[mn.pos].stock * v[mn.pos].cost;
                    v[mn.pos].stock = 0;
                    mn.value = 2147483647;
                    mn.pos = 0;
                    for (j=1; j<=k; j++)
                    {
                        if (v[s[j].type].cost <= mn.value && v[s[j].type].stock)
                        {
                            mn.value = v[s[j].type].cost;
                            mn.pos = s[j].type;
                            break;
                        }
                    }
                    if (mn.value == 2147483647 && cust.dishes)
                    {
                        cost = 0;
                        cust.dishes = 0;
                    }
                }
                else
                {
                    cost += v[mn.pos].cost * cust.dishes;
                    v[mn.pos].stock -= cust.dishes;
                    cust.dishes = 0;
                }
            }
        }
        cout << cost << "\n";
    }
}

我知道我还没有写好我的代码，看上去最好，但我想它也可以。

B.农历新年与食品订购

餐馆“爱丽丝”提供n种类的食物。i-th类型的成本总是c_i。一开始，这家餐厅有足够的原料供应i-th那类的正宗D9-th菜肴。除夕夜，m的顾客们会一个接一个地来艾丽斯家，j-th的顾客会点一些t_j-th的d_j菜。(i+1)-st客户只会在i-完全为客户服务之后才会出现。假设还有剩下的r_i类i-th类菜肴(最初是r_i = a_i)。当客户订购1的i-th类菜肴时，将处理以下原则。

1. 如果是r_i > 0，顾客就会得到i-th那类的1菜。这道菜的价格是c_i。同时，r_i将被1降低。
2. 否则，如果有的话，顾客将得到最便宜的现有食物的1菜。如果有多种最便宜的食物，最便宜的就是指数最小的食物。该成本将是所提供的菜肴的成本，而相应的菜肴的剩馀将通过1降低。
3. 如果没有更多的菜，顾客就会生气地离开。因此，无论以前提供了多少菜，顾客的成本都是0。

如果顾客在提供d_j菜肴后不离开，客户的成本将是这些d_j菜肴的成本之和。请确定每个m客户的总成本。输入第一行包含两个整数n和m ( 1 ≤ n, m ≤ 10^5)，分别表示不同种类的食物数量和客户数量。第二行包含n正整数a_1, a_2,\ldots, a_n (1 ≤ a_i ≤ 10^7)，其中a_i表示i-th类菜肴的初始余数。第三行包含n正整数c_1, c_2, \ldots, c_n (1 ≤ c_i ≤ 10^6)，其中c_i表示i-th类菜肴的成本。下面的m行分别描述m客户的订单。j-th行包含两个正整数t_j和d_j (1 ≤ t_j ≤ n，1 ≤ d_j ≤ 10^7)，分别表示食物的种类和j-th客户订单的菜肴数量。输出打印m行。在j-th行中，打印j-th客户的成本。要求

• 每次测试的时间限制:2秒
• 每次测试的内存限制: 256兆字节
• 输入:标准输入
• 产出:标准产出

从评估人员花费在评估超过测试时间限制的时间开始，我就认为我的程序被困在某个地方了。希望能从你们那里得到一些建议！

编辑:代码肯定会卡在某个地方，我只是替换了我对排序数组的旧的、效率低下的搜索，结果是一样的。

Answer 1

您有几个编译器警告：

24: error: ISO C++ forbids initialization of member ‘pos’
24: error: making ‘pos’ static
24: error: ISO C++ forbids in-class initialization of non-const static member ‘pos’
24: error: local class ‘struct main()::minim’ shall not have static data member ‘long int main()::minim::pos’
25: error: ISO C++ forbids initialization of member ‘value’
25: error: making ‘value’ static
25: error: ISO C++ forbids in-class initialization of non-const static member ‘value’
25: error: local class ‘struct main()::minim’ shall not have static data member ‘long int main()::minim::value’

不是有效的标题：

#include 

这个声明是错误的做法:参见：https://stackoverflow.com/q/1452721/14065的第二个答案是最好的。

using namespace std;

请给我一行报关单。

    long long stock, cost;

你在这里复制参数。

bool compare (sorted_food lhs, sorted_food rhs)

传递const引用以避免复制。如果您正确地编写了上面的类型，您就会发现复制比传递引用要昂贵得多。

这看起来完全是垃圾：

    return (lhs.cost < rhs.cost && lhs.cost && rhs.cost);

让我们看看：

    A Cost  B Cost    A < B    B < A
       5      6         T        F           OK
       5      0         F        F           Hmmmm So they are equal?
       0      6         F        F           Hmmmm
       0      0         F        F           Hmmmm 

到底怎么回事！

    long long i,n,m,cost,d,j,k=1;

每行一个变量。只在需要时声明变量。这不是C89。您不需要声明顶部的所有变量。它没有给你速度利益，宣布他们全部在顶部。声明仅为一个字符的变量，给它们一个名称，这样我们就可以读取代码，这对速度没有好处。

如果您能够阅读代码，您就有更好的机会发现更好的算法。

这是一个有点古怪的方式写一个循环！

    for (i=1; i<=m; i++)

    // Normally written like this:
    for (int i=0; i < m; ++i)

是的，正如预期的那样，其余的都是不可读的，所以我不能建议一个更好的算法。