สมมติว่าเรามีสตริงตัวเลข S ความยาว n หลัก S แทนนาฬิกาดิจิทัลและสตริงทั้งหมดแสดงจำนวนเต็ม 0 ถึง 10^n - 1 หากมีหลักน้อยกว่า จะแสดง 0 นำหน้า ทำตามการดำเนินการ:
- ลดตัวเลขบนนาฬิกาลง 1 หรือ
- สลับตัวเลขสองหลัก
เราต้องการให้นาฬิกาแสดง 0 ด้วยจำนวนการดำเนินการน้อยที่สุด เราต้องนับจำนวนการดำเนินการที่ต้องใช้
เช่น ถ้าค่าที่ป้อนเข้าเป็น S = "1000" ผลลัพธ์จะได้ 2 เพราะเราสลับ 1 ตัวแรกกับ 0 ตัวสุดท้าย สตริงจะเป็น "0001" ตอนนี้ลดลง 1 ได้ "0000"
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ S x := หลักที่ตำแหน่ง S[n - 1] สำหรับ i := 0 เมื่อ i <= n - 2 เพิ่ม i ทีละ 1 ทำ: ถ้า S[i] ไม่เท่ากับ '0' แล้ว: x := x + (หลักที่ตำแหน่ง S[i]) + 1 คืนค่า x
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; int solve(string S) { int n = S.size(); int x = S[n - 1] - '0'; for (int i = 0; i <= n - 2; i++) if (S[i] != '0') x = x + S[i] + 1 - '0'; return x; } int main() { string S = "1000"; cout << solve(S) << endl; }
ข้อมูลนำเข้า
"1000"
ข้อมูลส่งออก
2
