C++のすべての奇数の長さのサブリストの中央値の合計を見つけるプログラム

numsという数値のリストがあるとすると、指定されたリストのすべての奇数長のサブリストの中央値の合計を見つける必要があります。

したがって、入力がnums =[2、4、6、3]のようである場合、奇数の長さのサブリストは− [2]、[4]、[6]、[3]であるため、出力は23になります。 [2、4、6]、[4、6、3]なので、中央値の合計は2 + 4 + 6 + 3 + 4 + 4 =23

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

• ret：=0

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

  • que_maxと呼ばれる優先キューを定義します

  • que_min

    と呼ばれる別の優先キューを定義します

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

    • nums[j]をque_maxに挿入します

    • que_maxのサイズ>=2の場合、実行-

      • que_maxの一番上の要素をque_minに挿入します

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

    • （que_minのサイズが0ではなく、que_maxの最上位要素> que_minの最上位要素）、do-

      • a：=que_maxの最上位要素、que_maxから最上位要素を削除

      • b：=que_minの最上位要素、que_minから最上位要素を削除

      • bをque_maxに挿入します

      • que_minにaを挿入します

    • imod2がjmod2と同じ場合、-

      • ret：=ret+que_maxの最上位要素

• retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
   int ret = 0;
   for (int i = 0; i < nums.size(); i++) {
      priority_queue<int> que_max;
      priority_queue<int, vector<int>, greater<int>> que_min;
      for (int j = i; j < nums.size(); j++) {
         que_max.push(nums[j]);
         while (que_max.size() - que_min.size() >= 2) {
            que_min.push(que_max.top());
            que_max.pop();
         }
         while (que_min.size() && que_max.top() > que_min.top()) {
            int a = que_max.top();
            que_max.pop();
            int b = que_min.top();
            que_min.pop();
            que_max.push(b);
            que_min.push(a);
         }
         if (i % 2 == j % 2) {
            ret += que_max.top();
         }
      }
   }
   return ret;
}
int main(){
   vector<int> v = {2, 4, 6, 3};
   cout << solve(v);
}

入力

{2, 4, 6, 3}

出力

23