Số tập hợp tối thiểu với số nhỏ hơn Y trong C++

Đề bài

Cho một chuỗi các chữ số liên tiếp và một số Y, nhiệm vụ là tìm số tập hợp tối thiểu sao cho mọi tập hợp tuân theo quy tắc sau:

• Tập hợp phải chứa các số liên tiếp
• Không được sử dụng chữ số nào hơn một lần
• Số trong tập hợp không được lớn hơn Y

Ví dụ

Nếu str = "1234" và Y = 20 thì câu trả lời là 3 với các tập hợp sau:

{12} {3} và {4}

Thuật toán

• Chuyển chuỗi thành số
• Nếu số không lớn hơn Y, đánh dấu f = 1
• Nếu số vượt quá Y, tăng count nếu f = 1 và khởi tạo lại f = 0 và cũng khởi tạo num = s[i]-'0' hoặc num = 0
• Sau khi duyệt hết chuỗi, tăng count nếu f = 1

Ví dụ

#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 << "Tập hợp tối thiểu = " << getMinSets(str, y) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Tập hợp tối thiểu = 3