Program C++: Kira bilangan operasi yang diperlukan untuk meletakkan elemen dengan indeks kurang daripada nilai

Katakan kita mempunyai tatasusunan A yang mengandungi n elemen. Kita boleh melakukan operasi ini beberapa kali -

• Pilih mana-mana integer positif k

• Pilih mana-mana kedudukan dan Sisipkan k

• pada kedudukan ini, urutan berubah, dan kami meneruskan urutan ini dalam operasi seterusnya.

ul>

Kita mesti mencari bilangan minimum operasi yang diperlukan untuk memenuhi syarat: untuk semua i dalam julat 0 hingga n- 1, A[i]

Jadi jika input katakan A = [1, 2, 5, 7, 4], maka output akan menjadi 3 kerana kita boleh melakukan sesuatu seperti: [1,2,5,7, 4] kepada [1,2,3,5,7,4] kepada [1,2,3,4,5,7,4] kepada [1,2,3,4,5,3,7,4] .

Langkah h2>

Untuk menyelesaikan masalah ini kami akan ikuti langkah berikut -

maxj := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   maxj := maximum of maxj and (A[i] - i - 1)
return maxj

Contoh

#🎜 Jom lihat lihat pelaksanaan berikut untuk mendapatkan pemahaman yang lebih baik −

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int maxj = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      maxj = max(maxj, A[i] - i - 1);
   }
   return maxj;
}
int main() {
   vector<int> A = { 1, 2, 5, 7, 4 };
   cout << solve(A) << endl;
}

Input

{ 1, 2, 5, 7, 4 }

Output

3

Atas ialah kandungan terperinci Program C++: Kira bilangan operasi yang diperlukan untuk meletakkan elemen dengan indeks kurang daripada nilai. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!