สมมติว่าเรามีสตริงไบนารี S ที่มี n บิต ไม่มีศูนย์นำที่ซ้ำซ้อน เราสามารถดำเนินการสองแบบบน S ได้:
- สลับคู่ของบิตที่อยู่ติดกันได้
- แทนที่ "11" ทั้งหมดด้วย "1"
ให้ val(S) เป็นค่าทศนิยมของ S เราต้องหาสตริงที่ถูกต้องและน้อยที่สุด โดยสตริงถูกต้อง A น้อยกว่า B เมื่อ val(A) < val(B)
เช่น ถ้าอินพุตคือ S = "1001" เอาต์พุตจะเป็น 100 เพราะสามารถดำเนินการได้ดังนี้: "1001" → "1010" → "1100" → "100"
ขั้นตอนการแก้ปัญหา
n := ขนาดของ S
res := สตริงว่าง
res := res + S[0]
for i := 1 ถึง n-1:
if S[i] == '0':
res := res + "0"
return res
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
string solve(string S) {
int n = S.size();
string res = "";
res += S[0];
for (int i = 1; i < n; i++) {
if (S[i] == '0') {
res += "0";
}
}
return res;
}
int main() {
string S = "1001";
cout << solve(S) << endl;
}อินพุต
"1001"
เอาต์พุต
100
