leetcode 第126场双周赛第二题

这道题一开始并没有想到怎么做，当时考虑到是不是贪心的做法，结果并不是，其实还是暴力模拟的过程。当时确实想到了模拟，但是在二维vector排序方面并不是很清楚，所以并没有下决定模拟，也没做出来。

那么正好作为一个教训，查询了关于二维vector数组的排序问题，这里的排序是根据一维的数字大小升序排序的，而这个时候对应的二维中的数字不是不动的，而是随着一维的变化进行改变的，它们排序之后依然是对应关系。

讲一下解题思路：

首先我们看到每个数组的数字都必须对应状态，状态的话需要一个数组进行实现标记。然后，我们还需要存储每次操作之后的sum是多少，这个时候开一个数组。由于我们需要用到下标和元素之间的关系，可能会想到用哈希表映射，但并没法把元素进行排序了。所以这里选择用vector二维数组进行存储这个映射关系。

然后就是对于这个二维数组的读入对应关系，进行排序，排序完之后就是从小到大元素的顺序以及对应的下标了。

对于我们如何记录和的问题，我们可以反过来想，也就是我们首先把所有元素加起来，也就是所有元素的和先记录下来，然后我们在操作标记的时候再依次减去就行了，这样也是一种方法。

好了，预处理结束之后，我们开始模拟了：

首先就是对于queries的遍历，我们首先就是需要确定queries中的第一维元素中存储的下标元素我们是否已经遍历过了（这里需要对于原数组中进行确认，而不是我们存储的那个对应关系的数组），如果没有，我们就直接标记现在遍历过了，然后再在总和sum中减去这个元素，记录下接下来我们需要操作的次数，也就是queries下一维存储的数字。

这个时候就轮到我们刚刚存储的二维数组排上用场了，这个时候我们的一维空间都是顺序排出来的，所以是从最小元素开始的，我们只需要从头开始遍历，确认有没有标记，然后再判断是否去减去元素就行了。不要忘了记录每一组操作之后的sum的值。

class Solution {
public:
    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n=nums.size();
        vector<vector<int>>ans;
        vector<long long>res;
        vector<bool>st(n);
        long long sum=accumulate(nums.begin(),nums.end(),0LL);
        for(int i=0;i<n;i++){
            ans.push_back({nums[i],i});
        }
        sort(ans.begin(),ans.end());
        int j=0;
        int count=0;
        for(int i=0;i<queries.size();i++){
            if(!st[queries[i][0]]){
                st[queries[i][0]]=true;
                sum-=nums[queries[i][0]];
            }
            count=queries[i][1];
            while(count>0&&j<n){
                int value=ans[j][0];
                int index=ans[j][1];
                j++;
                if(!st[index]){
                    sum-=value;
                    st[index]=true;
                    count--;
                }
                else continue;

            }
            res.push_back(sum);
        }
        return res;
    }
};