C++で並べ替えられた行を持つ行列のK番目に小さい合計を見つける

matと呼ばれる1つのm*n行列があり、整数kの場合、matの行は降順ではない順序で並べ替えられます。各行から正確に1つの要素を選択して、配列を形成できます。考えられるすべての配列の中で、K番目に小さい配列の合計を見つける必要があります。

したがって、入力がmat =[[1,3,11]、[2,4,6]]

k =5の場合、出力は7になります。これは、各行から1つの要素を選択すると、最初のk個の最小の合計が[1,2]、[1,4]、[3,2]、[3,4]になるためです。 、[1,6]。ここで5番目の合計は7です。

これを解決するには、次の手順に従います-

• 1つの優先キューpqを定義する

• 1つの2D配列mを定義します

• 関数update（）を定義します。これにより、配列v、i、okがfalseで初期化されます。

• iがvのサイズと同じである場合、-

  • okがfalseの場合、-

    • 戻る

  • 戻る

  • 初期化j：=0の場合、j

    • 合計：=合計+ m [j、v [j]]

  • アレイの温度を定義し、vをその中にコピーします

  • 最初に合計をtempに挿入します

  • 温度をpqに挿入

  • 戻る

• （v [i]を1増やします）

• okがfalseで、v [i]

  • update（v、i + 1、true）

• update（v、i + 1、true）

• update（v、i + 1、ok）

• メインの方法から、次のようにします-

• m：+与えられた行列

• ret：=0

• n：=mの行数

• z：=mの列数

• 初期化i：=0の場合、i

  • ret：=ret + m [i、0]

• サイズnのアレイ温度を定義します

• 最初にretをtempに挿入します

• 温度をpqに挿入

• 1つのセットを定義する

• kがゼロ以外の場合、反復ごとにkを1ずつ減らし、-

  を実行します。

  • 配列temp=top of pq

    を定義します

  • pqから要素を削除する

  • 温度をsに挿入

  • ret：=temp [0]

  • tempからtempの最初の要素を削除します

  • update（temp、0）

  • （pqが空ではなく、pqの最上位要素がsのメンバーである場合）、do-

    • pqから要素を削除する

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(vector <int>& a, vector <int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   priority_queue<vector<int>, vector<vector<int> >, Cmp> pq;
   vector<vector<int> > m;
   int z;
   void update(vector<int>& v, int i, bool ok = false){
      if (i == v.size()) {
         if (!ok)
         return;
         int sum = 0;
         for (int j = 0; j < v.size(); j++) {
            sum += m[j][v[j]];
         }
         vector<int> temp(v.begin(), v.end());
         temp.insert(temp.begin(), sum);
         pq.push(temp);
         return;
      }
      v[i]++;
      if (!ok && v[i] < z)
      update(v, i + 1, true);
      v[i]--;
      update(v, i + 1, ok);
   }
   int kthSmallest(vector<vector<int> >& m, int k){
      this->m = m;
      int ret = 0;
      int n = m.size();
      z = m[0].size();
      for (int i = 0; i < n; i++) {
         ret += m[i][0];
      }
      vector<int> temp(n);
      temp.insert(temp.begin(), ret);
      pq.push(temp);
      set<vector<int> > s;
      while (k--) {
         vector<int> temp = pq.top();
         pq.pop();
         s.insert(temp);
         ret = temp[0];
         temp.erase(temp.begin());
         update(temp, 0);
         while (!pq.empty() && s.count(pq.top())) {
            pq.pop();
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,3,11},{2,4,6}};
   cout << (ob.kthSmallest(v, 5));
}

入力

{{1,3,11},{2,4,6}}

出力

7