Trong bài này, chúng ta sẽ thảo luận về vấn đề sắp xếp lại một dãy n số cho trước. Về cơ bản, chúng ta phải chọn các phần tử từ mảng. Để chọn từng phần tử, chúng tôi nhận được một số điểm sẽ được đánh giá bằng giá trị của phần tử hiện tại * một số phần tử được chọn trước phần tử hiện tại. Bạn nên chọn các phần tử để có được điểm tối đa. Ví dụ -
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 Phương pháp tiếp cận để tìm ra giải pháp
Nhìn vào ví dụ, chúng ta hiểu rằng để có được điểm tối đa, và chúng ta cần chọn các phần tử từ nhỏ nhất đến lớn nhất. Cách tiếp cận để tìm ra giải pháp là,
- Sắp xếp mảng đã cho theo thứ tự tăng dần.
- Bắt đầu chọn các phần tử từ chỉ mục 0 đến cuối.
- Tính số điểm bạn nhận được khi chọn từng phần tử.
Ví dụ
#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;
} Đầu ra
Maximum points: 63
Giải thích về đoạn mã trên
Mã C ++ này rất dễ hiểu. Đầu tiên, chúng tôi sắp xếp mảng và sau đó duyệt qua mảng bằng vòng lặp for và tính điểm đạt được bằng cách chọn từng phần tử từ đầu đến cuối.
Kết luận
Trong bài viết này, chúng ta thảo luận về vấn đề chọn phần tử trong một mảng để có được điểm tối đa trong đó điểm được tính bằng i * arr [i]. Chúng tôi áp dụng một cách tiếp cận tham lam để giải quyết vấn đề này và nhận được điểm tối đa. Cũng thảo luận về mã C ++ để làm tương tự, chúng ta có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như C, java, Python, v.v. Hy vọng bạn thấy bài viết này hữu ích.