C++ প্রোগ্রাম: A[i] ≤ i শর্ত পূরণের জন্য ন্যূনতম অপারেশন গণনা

একটি অ্যারে A দেওয়া আছে। অপারেশন: যেকোনো ধনাত্মক পূর্ণসংখ্যা k নির্বাচন করে যেকোনো পজিশনে ইনসার্ট করুন। A[i] ≤ i (০-ভিত্তিক) শর্ত পূরণ করতে ন্যূনতম কত অপারেশন লাগবে তা বের করতে হবে।

উদাহরণ

A = [1, 2, 5, 7, 4] → আউটপুট: 3

প্রক্রিয়া: [1,2,5,7,4] → [1,2,3,5,7,4] → [1,2,3,4,5,7,4] → [1,2,3,4,5,3,7,4]

সমাধানের ধাপসমূহ

প্রতিটি i-র জন্য (A[i] - i - 1) এর সর্বোচ্চ মান বের করুন। সেটিই ন্যূনতম অপারেশন সংখ্যা।

উদাহরণ

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

int solve(vector 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 A = {1, 2, 5, 7, 4}; 
    cout << solve(A) << endl; 
    return 0; 
}

ইনপুট

{1, 2, 5, 7, 4}

আউটপুট

3

ব্যাখ্যা

i=2: 5-2-1=2, i=3: 7-3-1=3, i=4: 4-4-1=-1। সর্বোচ্চ = 3।