ในบทความนี้ เราจะพูดถึงปัญหาของการจัดเรียงอาร์เรย์ของตัวเลข n ใหม่ โดยพื้นฐานแล้ว เราต้องเลือกองค์ประกอบจากอาร์เรย์ สำหรับการเลือกแต่ละองค์ประกอบ เราได้รับคะแนนบางส่วนที่จะประเมินโดยค่าขององค์ประกอบปัจจุบัน * องค์ประกอบจำนวนหนึ่งที่เลือกก่อนองค์ประกอบปัจจุบัน คุณควรเลือกองค์ประกอบเพื่อให้ได้คะแนนสูงสุด ตัวอย่างเช่น −
Input : arr[ ] = { 3, 1, 5, 6, 3 }
If we select the elements in the way it is given, our points will be
= 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
= 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
= 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
= 48(maximum)
Output : 48
Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63 แนวทางในการหาทางออก
จากตัวอย่าง เราเข้าใจเพื่อให้ได้คะแนนสูงสุด และเราต้องเลือกองค์ประกอบจากเล็กที่สุดไปหาใหญ่ที่สุด แนวทางในการหาแนวทางแก้ไขคือ
- เรียงลำดับอาร์เรย์ที่กำหนดจากน้อยไปหามาก
- เริ่มเลือกองค์ประกอบจากดัชนี 0 ถึงจุดสิ้นสุด
- คำนวณคะแนนที่คุณได้รับจากการเลือกแต่ละองค์ประกอบ
ตัวอย่าง
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main () {
int arr[] = { 2, 4, 7, 1, 8 };
int n = sizeof (arr) / sizeof (arr[0]);
// sorting the array
sort (arr, arr + n);
int points = 0;
// traverse the array and calculate the points
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
} ผลลัพธ์
Maximum points: 63
คำอธิบายของโค้ดด้านบน
รหัส C ++ นี้เข้าใจง่าย ขั้นแรก เรากำลังจัดเรียงอาร์เรย์ จากนั้นสำรวจอาร์เรย์โดยใช้ a for loop และคำนวณคะแนนที่ได้รับโดยการเลือกแต่ละองค์ประกอบตั้งแต่ต้นจนจบ
บทสรุป
ในบทความนี้ เราจะพูดถึงปัญหาในการเลือกองค์ประกอบในอาร์เรย์เพื่อให้ได้คะแนนสูงสุดโดย i * arr[i] คำนวณคะแนน เราใช้วิธีการที่โลภในการแก้ปัญหานี้และได้รับคะแนนสูงสุด พูดคุยเรื่องโค้ด C++ เพื่อทำเช่นเดียวกัน เราสามารถเขียนโค้ดนี้ในภาษาอื่นๆ เช่น C, java, Python เป็นต้น หวังว่าบทความนี้จะเป็นประโยชน์
