ทำให้อาร์เรย์เพิ่มขึ้นอย่างเคร่งครัดใน C ++

สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ arr1 และ arr2 ซึ่งสามารถเก็บตัวเลขจำนวนเต็มได้ เราต้องหาจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการทำให้ arr1 เพิ่มขึ้นอย่างเคร่งครัด ที่นี่ เราสามารถเลือกดัชนีได้ 2 ตัว 0 <=i

หากเรา caPending-3n ไม่ได้ทำให้อาร์เรย์ arr1 เพิ่มขึ้นอย่างเคร่งครัด ให้คืนค่า -1

ดังนั้น หากอินพุตเป็นเหมือน arr1 =[1,5,3,7,8], arr2 =[1,3,2,5] ผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถแทนที่ 5 ด้วย 2 ได้ อาร์เรย์จะเป็น [1,2,3,7,8]

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

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้อาร์เรย์ arr1, อาร์เรย์ arr2, i, j, ก่อนหน้า, อาร์เรย์ 2D หนึ่งรายการ dp,

• ถ้า i>=ขนาดของ arr1 แล้ว −

  • กลับ 1

• j =องค์ประกอบแรกของ subarray ของ arr2 จาก arr2[j] และบน

• ถ้า dp[i, j] ไม่เท่ากับ -1 แล้ว −

  • กลับ dp[i, j]

• ret :=ขนาดของ arr2 + 1

• ถ้าก่อนหน้า

  • ret :=ขั้นต่ำของ ret และแก้ปัญหา (arr1, arr2, i + 1, j, arr1[i], dp)

• ถ้า j <ขนาดของ arr2 แล้ว −

  • ret :=ขั้นต่ำของ ret และ 1 + แก้ (arr1, arr2, i + 1, j, arr2[j], dp)

• กลับ dp[i, j] =ret

• จากวิธีหลัก ให้ทำดังนี้ −

• จัดเรียงอาร์เรย์ arr2

• n :=ขนาดของ arr1

• m :=ขนาดของ arr2

• กำหนด dp อาร์เรย์ 2 มิติหนึ่ง dp ขนาด 2005 x 2005 และเติมด้วย -1

• ret :=แก้ (arr1, arr2, 0, 0, -inf, dp)

• return (ถ้า ret> ขนาดของ arr2 แล้ว -1 มิฉะนั้น ret - 1)

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
      if (i >= arr1.size())
         return 1;
      j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
      if (dp[i][j] != -1)
         return dp[i][j];
      int ret = arr2.size() + 1;
      if (prev < arr1[i]) {
         ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
      }
      if (j < arr2.size()) {
         ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
      }
      return dp[i][j] = ret;
   }
   int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
      sort(arr2.begin(), arr2.end());
      int n = arr1.size();
      int m = arr2.size();
      vector<vector<int> > dp(2005, vector<int>(2005, -1));
      int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
      return ret > arr2.size() ? -1 : ret - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
   cout << (ob.makeArrayIncreasing(v,v1));
}

อินพุต

{1,5,3,7,8}, {1,3,2,5}

ผลลัพธ์

1