โปรแกรมหาผลรวมของค่ามัธยฐานของรายการย่อยที่มีความยาวคี่ทั้งหมดใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องหาผลรวมของค่ามัธยฐานของรายการย่อยที่มีความยาวคี่ทุกรายการของรายการที่กำหนด

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 4, 6, 3] ผลลัพธ์จะเป็น 23 เนื่องจากรายการย่อยที่มีความยาวคี่คือ − [2], [4], [6], [3], [2, 4, 6], [4, 6, 3] ดังนั้นผลรวมของค่ามัธยฐานคือ 2 + 4 + 6 + 3 + 4 + 4 =23

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • กำหนดลำดับความสำคัญที่เรียกว่า que_max

  • กำหนดลำดับความสำคัญอื่นที่เรียกว่า que_min

  • สำหรับการเริ่มต้น j :=i เมื่อ j <ขนาดของ nums ให้อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • ใส่ nums[j] ลงใน que_max

    • ในขณะที่ขนาดของ que_max>=2 ทำ -

      • แทรกองค์ประกอบด้านบนของ que_max ลงใน que_min

      • ลบองค์ประกอบด้านบนออกจาก que_max

    • ในขณะที่ (ขนาดของ que_min ไม่ใช่ 0 และองค์ประกอบด้านบนของ que_max> องค์ประกอบด้านบนของ que_min) ทำ -

      • a :=องค์ประกอบด้านบนของ que_max ลบองค์ประกอบด้านบนออกจาก que_max

      • b :=องค์ประกอบด้านบนของ que_min ลบองค์ประกอบด้านบนออกจาก que_min

      • แทรก b ลงใน que_max

      • ใส่ a ลงใน que_min

    • ถ้าฉัน mod 2 เหมือนกับ j mod 2 แล้ว −

      • ret :=ret + องค์ประกอบด้านบนของ que_max

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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