C++の異なるリストから選択された要素間の最小の違いを見つけるためのプログラム

リストのリストがあるとすると、各リストから1つの値を選択し、選択した要素の最大数と最小数の差をとることによって形成できる最小の差を見つける必要があります。

したがって、入力がlists =[[30、50、90]、[85]、[35、70]]のような場合、出力は20になります。これは、90、85、70、および90-70 =20

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

• maxVal：=-inf

• ret：=inf

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

• n：=リストのサイズ

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

  • 配列リストを並べ替える[i]

  • {lists [i、0]、i、0}をpqに挿入します

  • maxVal：=リストの最大数[i、0]およびmaxVal

• pqのサイズはnと同じですが、-

  を実行します。

  • 配列temp=top of pq

    を定義します

  • pqから最上位の要素を削除します

  • ret：=retの最小値と（maxVal --temp [0]）

  • 温度の最後の要素を増やす

  • tempの最後の要素<リストのサイズ[temp[1]]の場合、<

    • maxVal：=maxValとlistsの最大値[temp[1]、tempの最後の要素]

    • temp [0]：=lists [temp [1]、tempの最後の要素]

    • 温度を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:
   int solve(vector<vector<int>>& lists) {
      int maxVal = INT_MIN;
      int ret = INT_MAX;
      priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
      int n = lists.size();
      for (int i = 0; i < n; i++) {
         sort(lists[i].begin(), lists[i].end());
         pq.push({lists[i][0], i, 0});
         maxVal = max(lists[i][0], maxVal);
      }
      while (pq.size() == n) {
         vector<int> temp = pq.top();
         pq.pop();
         ret = min(ret, maxVal - temp[0]);
         temp.back()++;
         if (temp.back() < lists[temp[1]].size()) {
            maxVal = max(maxVal, lists[temp[1]][temp.back()]);
            temp[0] = lists[temp[1]][temp.back()];
            pq.push(temp);
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& lists) {
   return (new Solution())->solve(lists);
}
int main(){
   vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
   cout << solve(v);
}

入力

{{30, 50, 90},{85},{35, 70}}

出力

20