สมมติว่าเรามีสตริง เราต้องย่อผลรวมของค่า ASCII ของอักขระแต่ละตัวให้เหลือน้อยที่สุด หลังจากลบทุกการเกิดขึ้นของอักขระบางตัว สมมติว่าสตริงได้รับเช่น "hello" ผลรวมของอักขระ ASCII คือ (104 + 101 + 108 + 108 + 111) =532 ตอนนี้ให้ตรวจสอบการปรากฏของอักขระแต่ละตัว
- h เกิดขึ้นครั้งเดียว ดังนั้นราคาคือ 1 * 104 =104
- e เกิดขึ้นครั้งเดียว ดังนั้นราคาคือ 1 * 101 =101
- l เกิดขึ้นครั้งเดียว ดังนั้นราคาคือ 2 * 108 =216
- o เกิดขึ้นครั้งเดียว ดังนั้นราคาคือ 1 * 111 =111
ที่นี่ l เกิดขึ้นตามระยะเวลาสูงสุดแล้ว ดังนั้นหากเราลบการเกิดของ l ทั้งหมด ค่าจะถูกย่อให้เล็กสุด ที่จริงแล้วเรากำลังลบค่าสูงสุดออกจากรายการด้านบน ที่นี่ผลลัพธ์สุดท้ายจะเป็น 532 – 216 =316
ตรรกะง่าย ๆ ในตอนแรกเราต้องนำผลรวม ASCII ของสตริง จากนั้นนับความถี่ของอักขระแต่ละตัวที่อยู่ในสตริง จากนั้นลบอักขระนั้นซึ่งทำให้เกิดค่าสูงสุดตามการเกิดขึ้น * ค่า ASCII ค่าที่ลบออกคือผลลัพธ์
ตัวอย่าง
#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);
} ผลลัพธ์
Minimized Sum: 316
