ข้อความโจทย์
กำหนดสตริงของตัวเลขต่อเนื่องและตัวเลข Y งานคือหาจำนวนเซตน้อยที่สุด ซึ่งทุกเซตต้องปฏิบัติตามกฎต่อไปนี้ −
- เซตควรประกอบด้วยตัวเลขที่ต่อเนื่องกัน
- ไม่สามารถใช้ตัวเลขซ้ำได้มากกว่าหนึ่งครั้ง
- ตัวเลขในเซตไม่ควรมากกว่า Y
ตัวอย่าง
ถ้า str = “1234” และ Y = 20 คำตอบคือ 3 ดังเซตที่สร้างได้ −
{12} {3} และ {4}
อัลกอริทึม
- แปลงสตริงเป็นตัวเลข
- ถ้าตัวเลขไม่มากกว่า Y ให้ตั้ง f = 1
- ถ้าตัวเลขเกิน Y ให้เพิ่มนับถ้า f = 1 และรีเซ็ต f เป็น 0 และเริ่มต้น num ใหม่เป็น s[i]-'0' หรือ num เป็น 0
- หลังวนลูปผ่านสตริงหมด ให้เพิ่มนับถ้า f เป็น 1
ตัวอย่าง
#include <iostream> #include <string> using namespace std; int getMinSets(string str, int y) { int cnt = 0; int num = 0; int l = str.length(); int f = 0; for (int i = 0; i < l; ++i) { num = num * 10 + str[i] - 48; if (num <= y) { f = 1; continue; } if (f) { ++cnt; } num = str[i] - '0'; f = 0; if (num <= y) { f = 1; } else { num = 0; } } if (f) { ++cnt; } return cnt; } int main() { string str = "1234"; int y = 20; cout << "Minimum sets = " << getMinSets(str, y) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Minimum sets = 3
