Skip to main content

排列组合（求30的倍数）

tip

输入一个数，比如201，让数字随意组合，是否能组合出30的倍数，如果能够组合成30的倍数，就输出最大的倍数，不能就输出-1

例如输入201可以随意组合成

201，210，012，021，102，120等数字

其中120，210都是30的倍数，由于要找最大的，所以答案是210

输入样例：201 输出样例：210

参考代码​

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int maxx = 0, flag = 0;
    sort(s.begin(), s.end());
    do {
        int now = 0;
        for (int i = 0; i < s.size(); i++) {
            now = now * 10 + s[i] - '0';
        }
        if (now % 30 == 0) {
            flag = 1;
            maxx = max(maxx, now);
        }
    } while (next_permutation(s.begin(), s.end()));
    if (flag == 1) {
        cout << maxx << endl;
        return 0;
    }
    else {
        cout << -1 << endl;
    }
}

题解​

使用C++ STL提供的排列组合模版

首先将代排列组合的字符串或数组进行排序

sort(list.begin(), list.end());

使用排列组合模版

do {
	something();
} while (next_permutation(list.begin(), list.end()));

此时，在每一个do循环中，list按从小到大的顺序进行排列组合遍历