คำชี้แจงปัญหา
ให้ชุดตัวเลขต่อเนื่องกันและตัวเลข 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
