时间戳

首页 > 解决方案 > 如何擦除向量或矩阵向量中的元素

c++ - 如何擦除向量或矩阵向量中的元素

问题描述

嘿，我正在尝试擦除向量向量/很可能是由向量组成的矩阵中的一个元素，所以我搜索了堆栈溢出，但它没有任何答案，我也无法在网上找到它，所以我想在这里问。好吧，我是编程新手，我正在尝试解决 google kick start 2020 Round-A QUESTION。

所以我写了一个代码，它的作用类似于堆栈，我没有使用堆栈，但尝试使用向量实现它，但无法擦除第 i 个向量第 n 个位置的元素。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#define ans(x,y) "Case #"<<x<<": "<<y<<"\n"
using namespace std;
int main(int argc, char *argv[])
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int TC;
    cin>>TC;
    int k=1;
    while(TC--){
        int Stacks,Plates,Max;
        cin>>Stacks>>Plates>>Max;
        vector<vector<int>>S_Plates;
        for(int i=0;i<Stacks;i++){
            vector<int>vec;
            for(int j=0;j<Plates;j++){
                int Dat;
                cin>>Dat;
                vec.push_back(Dat);
            }
            S_Plates.push_back(vec);
        }
        int Cnt=0,Beauty=0;
        while(Cnt!=Plates){
            int mx=0;
            int SNo=0;
            for(int i=0;i<Stacks;i++){
                mx=(mx,S_Plates[i][0]);
                if(mx==S_Plates[i][0])
                    SNo=i;
            }
            Beauty+=(mx);
        // Well Got Stucked Here    S_Plates.erase(S_Plates.begin()+SNo[0]);
            Cnt++;
        }
        cout<<ans(k,Beauty);
        k++;
    }
}

好吧，为了理解代码，请参考我上面链接的问题。

所以请让我知道我该怎么做。

PS：抱歉英语不好和代码不好

标签： c++

解决方案

擦除可以如下执行：

S_Plates[SNo].erase(S_Plates[SNo].begin());

如评论中所示，其他地方需要进行一些修改。

请注意，擦除是一项代价高昂的功能，在这里毫无用处：您可以改用索引。（每堆一个）

然而，这种贪心算法并没有提供好的结果。例如，考虑

Stacks (N) = 3; Plates (K) = 2; Max (P) = 2; 
S[0] = {1, 100}, S[1]={2, 2}, S[2] = {2, 2}

您的程序返回 4 而不是 101。

解决方案是实现一个DP算法。

Cumul[N][P]让我们定义一个初始化为 0的数组。

然后

i = 0 to N-2
Cumul[i+1][j] = max (Cumul[i][j], Cumul[i][j-k], A[i][0] + .. A[i][k-1]), for j =0 to P and k = 0 to K

复杂度为 O(PNK)。

推荐阅读