Chúng ta được cung cấp một mảng các số nguyên dương và âm cùng một số K. Nhiệm vụ là tìm tổng lớn nhất của mảng sau K phép thay đổi trên các phần tử của nó. Mỗi phép thay đổi đơn lẻ nhân một phần tử với -1.
Phương pháp tiếp cận
Cách tiếp cận được sử dụng là chuyển đổi mọi số âm thành số dương. Nếu có N số âm, chúng ta sẽ sắp xếp mảng:
Nếu N < K: Sau N phép toán, mọi phần tử đều thành dương, và chúng ta còn lại K-N phép toán.
Nếu K-N là chẵn: Các phép thay đổi dấu còn lại không có tác động, không làm gì cả.
Nếu K-N là lẻ: Đổi dấu của số nhỏ nhất (sẽ trở thành âm) nhưng tổng thể vẫn tối đa.
Nếu N > K: Đổi dấu của K số âm và cộng mảng. Tổng sẽ là tối đa.
Ví dụ 1
Đầu vào: Arr[] = { 0, -2, 6, 4, 8, 2, -3 }, K = 4
Đầu ra: Tổng mảng tối đa là: 25
Giải thích: 4 thay đổi trong các phần tử:
1. 0, 2, 6, 4, 8, 2, -3 (-2 thành 2) 2. 0, 2, 6, 4, 8, 2, 3 (-3 thành 3) 3. 0, -2, 6, 4, 8, 2, 3 (2 thành -2) 4. 0, 2, 6, 4, 8, 2, 3 (-2 thành 2) Tổng tối đa là 25
Ví dụ 2
Đầu vào: Arr[] = { -1, -2, -3, -4, -5, -6, -7 }, K = 4
Đầu ra: Tổng mảng tối đa là: 16
Giải thích: 4 thay đổi trong các phần tử:
1. -1, -2, -3, -4, -5, -6, 7 (-7 thành 7) 2. -1, -2, -3, -4, -5, 6, 7 (-6 thành 6) 3. -1, -2, -3, -4, 5, 6, 7 (-5 thành 5) 4. -1, -2, -3, 4, 5, 6, 7 (-4 thành 4) Tổng tối đa là 16
Cách triển khai trong chương trình
- Mảng nguyên Arr[] lưu trữ các số nguyên.
- Biến nguyên 'size' lưu độ dài mảng và K được khởi tạo.
- Hàm returnSum(int arr[], int n, int k) nhận mảng, kích thước và k, trả về tổng tối đa sau đúng k phép toán.
- Đầu tiên sắp xếp mảng bằng sort(arr, arr+n).
- Áp dụng phép toán arr[i]*-1 cho tất cả phần tử âm cho đến khi hết mảng hoặc k bằng 0.
- Nếu k nhỏ hơn số phần tử âm, bước trên sẽ đổi dấu k phần tử âm.
- Nếu k lớn hơn, kiểm tra k còn lại là lẻ hay chẵn.
- Nếu k còn lại là lẻ: đổi dấu phần tử nhỏ nhất một lần (nhân -1 số lần lẻ tương đương một lần).
- Nếu k còn lại là chẵn: arr[i]*-1 không có tác động. Không làm gì.
- Tính tổng toàn bộ mảng và trả về kết quả.
Mã ví dụ
#include <bits/stdc++.h>
using namespace std;
int returnSum(int arr[], int n, int k) {
// Sắp xếp các phần tử mảng
sort(arr, arr + n);
// Đổi dấu các phần tử âm
// bắt đầu từ nhỏ nhất
// Vòng lặp này đổi dấu phần tử âm
// mỗi k một phần tử âm thành dương
for (int i = 0; i < n; i++)
if (k > 0 && arr[i] < 0) {
arr[i] = arr[i] * -1;
k--;
}
// Nếu k khác 0 và lẻ, đổi dấu phần tử nhỏ nhất
// một lần vì tương đương đổi dấu số lần lẻ
if (k % 2 == 1) {
int min = arr[0];
int pos = 0; // chỉ số phần tử nhỏ nhất
for (int i = 1; i < n; i++)
if (arr[i] < min) {
min = arr[i];
pos = i;
}
arr[pos] *= -1;
}
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
int main() {
int Arr[] = { -3, 4, -3, 6, 8 };
int size = 5;
int K = 4;
cout << "Tổng mảng tối đa sau chính xác k thay đổi: "
<< returnSum(Arr, size, K) << endl;
return 0;
}
Đầu ra
Tổng mảng tối đa sau chính xác k thay đổi: 24