ข้อความโจทย์
กำหนดสตริงไบนารี ซึ่งเราสามารถพลิก 1 ทั้งหมดในส่วนซ้าย และ 0 ทั้งหมดในส่วนขวา งานคือคำนวณจำนวนการพลิกขั้นต่ำที่จำเป็นเพื่อทำให้ 1 ทั้งหมดอยู่ซ้ายและ 0 ทั้งหมดอยู่ขวา
ตัวอย่าง
สตริงไบนารีที่กำหนดคือ 0010101 ในสตริงนี้มี 1-bit 3 ตัว และ 0-bit 4 ตัว เราต้องพลิก 4 บิตที่ไฮไลท์ เพื่อทำให้ 1 ทั้งหมดอยู่ซ้ายและ 0 ทั้งหมดอยู่ขวา ดังนี้ −
0010101
หลังจากพลิกสตริงจะกลายเป็น −
1110000
อัลกอริทึม
- วนลูปสตริงจากซ้ายไปขวา และคำนวณจำนวนการพลิกที่ต้องการเพื่อแปลง 0 ทั้งหมดเป็น 1
- วนลูปสตริงจากขวาไปซ้าย และคำนวณจำนวนการพลิกที่ต้องการเพื่อแปลง 1 ทั้งหมดเป็น 0
- วนลูปผ่านตำแหน่งทั้งหมดระหว่างบิต และหาค่าต่ำสุดของ (การพลิก 0 + การพลิก 1)
ตัวอย่าง
#include <iostream> #include <string> #include <climits> using namespace std; int minFlips(string binaryString) { int n = binaryString.length(); int flipCnt, zeroFlips[n], oneFlips[n]; flipCnt = 0; for (int i = 0; i < n; ++i) { if (binaryString[i] == '0') { ++flipCnt; } zeroFlips[i] = flipCnt; } flipCnt = 0; for (int i = n - 1; i >= 0; --i) { if (binaryString[i] == '1') { ++flipCnt; } oneFlips[i] = flipCnt; } int minFlips = INT_MAX; for (int i = 1; i < n; ++i) { int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) { minFlips = sum; } } return minFlips; } int main() { string binaryString = "0010101"; cout << "Minimum flips: " << minFlips(binaryString) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Minimum flips: 4
