c++ - 看不懂迭代器的问题？

Question

The problem指出我们必须找到要删除的最小学生数，以便第 i 个学生可以通过考试。所以我基本上是将学生添加到一个 multiset 中，因为它存储排序后的值，当排序后的总和大于要求的分数时，我们将其减去并移至下一个。

输入问题:

3 4 3 9 1 1 9 8 9

m:通过所需的分数为 14

这里输入的第 6 个索引是 9，它没有被添加到多重集中，正在以某种方式被删除。

运行有问题的输入时我得到的输出:

0 0 0 ;4--;3-- 2 ;9-- 1 ;9-- 1 ;9--;4--;9-- 3 ;9--;9--;9-- 3 ;9--;9--;9--;9-- 4

:""-- 中的值包含从总和中减去的 *x，还有一个额外的 9，但我不知道如何计算？

multiset<int> st;
    int setsum =0;
    for(int i=0;i<n;i++)
    {
        int sum = setsum+ar[i];
        if((sum)<=m)
        {
            cout<<"0 ";
        }
        else
        {
            //cout<<sum<<"-*";
            int cnt = 0;
            auto x = st.rbegin();
            while(sum>m)
            {
                sum -= *x;
                //cout<<";"<<*x<<"--";
                x--;
                //if(i==3)
                    //cout<<*x<<"++";
                cnt++;
            }
            cout<<" "<<cnt<<" ";
        }
        st.emplace(ar[i]);
        setsum += ar[i];
    }

Answer 1

可能不是唯一的问题，但我不得不注意到您使用反向迭代器时的两个主要错误:

1. 您递减迭代器 (--x) 而不是递增它 (++x)；反向迭代器的全部意义在于方向是相反的，因此您应该递增迭代器以通过 st 向后移动。您使用 --x 的唯一原因是，如果您有双向迭代器并且想要以与“自然”迭代顺序相反的方式移动(因此正向迭代器将向后运行，而反向迭代器将向前运行)。
2. 你永远不会检查你是否到达了 st 的末尾；如果您在 sum > m 之前跑完 st 的末尾(我们没有 m 的定义，因此无法判断这种情况是否存在在结束 st 之前必然为真)，你遇到了未定义的行为。最简单的解决方法是简单地将测试更新为 while (sum > m && x != st.rend())，尽管这可能会影响您以后的代码逻辑(因为现在退出循环不是不能保证 sum 小于或等于 m)，需要进一步测试。