Giả sử chúng ta có một chuỗi. Chúng ta phải giảm thiểu tổng các giá trị ASCII của mỗi ký tự đối với chuỗi, sau khi loại bỏ mỗi lần xuất hiện của một ký tự cụ thể. Giả sử một chuỗi được đưa ra như “hello”, tổng các ký tự ASCII là (104 + 101 + 108 + 108 + 111) =532. Bây giờ hãy kiểm tra số lần xuất hiện của mỗi ký tự.
- h đã xảy ra một lần, vì vậy chi phí là 1 * 104 =104
- e đã xảy ra một lần, vì vậy chi phí là 1 * 101 =101
- l đã xảy ra một lần, vì vậy chi phí là 2 * 108 =216
- o đã xảy ra một lần, vì vậy chi phí là 1 * 111 =111
Ở đây l đã xảy ra khoảng thời gian lớn nhất, vì vậy nếu chúng ta loại bỏ tất cả các lần xuất hiện của l, thì giá trị sẽ nhỏ nhất. Vì vậy, thực sự chúng tôi đang xóa giá trị tối đa khỏi danh sách trên. Ở đây kết quả cuối cùng sẽ là 532 - 216 =316
Logic rất đơn giản lúc đầu chúng ta phải lấy tổng ASCII của chuỗi. Sau đó, đếm tần suất của mỗi ký tự hiện diện trong chuỗi, sau đó xóa ký tự đó đang đóng góp giá trị tối đa là giá trị * ASCII xuất hiện. Giá trị bị trừ là kết quả.
Ví dụ
#include <iostream>
using namespace std;
int minASCIISum(string str, int len) {
int max_val = INT_MIN, sum = 0;
int frequency[26] = { 0 };
for (int i = 0; i < len; i++) {
frequency[str[i] - 'a']++;
sum += (int)str[i];
}
for (int i = 0; i < 26; i++)
max_val = max(max_val, frequency[i] * (i + 'a'));
return (sum - max_val);
}
int main() {
string str = "hello";
int n = str.length();
cout << "Minimized Sum: " << minASCIISum(str, n);
} Đầu ra
Minimized Sum: 316