สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ เราสามารถดำเนินการได้ไม่จำกัดครั้ง:
- เลือกจำนวนเต็มบวก k ใดๆ
- เลือกตำแหน่งใดๆ ในลำดับและแทรก k เข้าไปที่ตำแหน่งนั้น
- ลำดับเปลี่ยนไป เราดำเนินต่อกับลำดับนี้ในครั้งถัดไป
เราต้องหาจำนวนการดำเนินการขั้นต่ำที่ต้องใช้เพื่อให้เงื่อนไข A[i] <= i สำหรับทุก i ในช่วง 0 ถึง n-1 เป็นจริง
เช่น ถ้าค่าที่ป้อนเข้าเป็น 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]
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
maxj := 0 n := ขนาดของ A สำหรับ i := 0 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: maxj := max(maxj, A[i] - i - 1) คืนค่า maxj
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#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; }
ข้อมูลนำเข้า
{ 1, 2, 5, 7, 4 }
ข้อมูลส่งออก
3
