NSUOJ 2697
程序员文章站
2022-07-12 15:53:07
...
Description
众所周知，飛機飛过天空学长喜欢听*的歌(听天空之城就知道为什么了)，连2016年发行的公益专辑《8》也不例外(但是大多数人难以接受)。大数nsir也很喜欢这张专辑，nsir很大，他可以从0到10100之间任意改变,当他听到这张专辑的时候他在想一个问题，他想让自己每一位的数字重新排列，这个排列后的new_nsir能够被8整除，问最大的new_nsir是多少。如果不满足，new_nsir=-1。
Input
多组输入
每行输入一个nsir(0<=nsir<=10100)
Output
输出new_nsir
Sample Input
0
1
480
Sample Output
0
-1
840
模拟题
一个数>1000 时，只要后三位数能被8整除，那么它就能被8整除
将1000以内能被8的数存下来，然后遍历一遍找到最大的
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
int len;
int cnt = 0;
int cal[1000];
bool cmp(char a, char b) {
return a > b;
}
void check() {
for (int i = 0; i <= 1000; i++)
if (i % 8 == 0)
cal[cnt++] = i;
}
void copy(int a[], int num[]) {
for (int i = 0; i < 10; i++)
a[i] = num[i];
}
int main() {
check();
char s[110];
while (cin >> s) {
char ans[110];
len = strlen(s);
for (int i = 0; i < len; i++)
ans[i] = '0';
ans[len] = '\0';
int maxn = -1;
if (len == 1) {
if ((s[0] - '0') % 8 == 0)
printf("%c\n", s[0]);
else
printf("-1\n");
}
else if (len == 2) {
if (((s[0] - '0') * 10 + s[1] - '0') % 8 == 0)
printf("%c%c\n", s[0], s[1]);
else if (((s[1] - '0') * 10 + s[0] - '0') % 8 == 0)
printf("%c%c\n", s[1], s[0]);
else
printf("-1\n");
}
else {
char temp[10];
char str[110];
int a[10];
int num[10] = { 0 };
for (int i = 0; i < len; i++)
num[s[i] - '0']++;
int flag = 1;
for (int i = 0; i < cnt; i++) {
temp[0] = cal[i] / 100 + '0';
temp[1] = (cal[i] % 100 - cal[i] % 10) / 10 + '0';
temp[2] = cal[i] % 10 + '0';
temp[3] = '\0';
if (temp[0] == temp[1] && temp[1] == temp[2]) {
if (num[temp[0] - '0'] > 2) {
copy(a, num);
a[temp[0] - '0'] -= 3;
int tot = 0;
for (int i = 0; i < 10; i++) {
while (a[i] > 0) {
str[tot++] = char(i + '0');
a[i]--;
}
}
str[tot] = '\0';
sort(str, str + tot, cmp);
str[tot++] = temp[0], str[tot++] = temp[0], str[tot++] = temp[0];
str[tot] = '\0';
if (strlen(ans) == strlen(str) && strcmp(ans, str) <= 0) {
strcpy(ans, str);
flag = 0;
}
}
}
else if (temp[0] == temp[1]) {
if (num[temp[0] - '0'] > 1 && num[temp[2] - '0']) {
copy(a, num);
a[temp[0] - '0'] -= 2;
a[temp[2] - '0']--;
int tot = 0;
for (int i = 0; i < 10; i++) {
while (a[i] > 0) {
str[tot++] = char(i + '0');
a[i]--;
}
}
str[tot] = '\0';
sort(str, str + tot, cmp);
str[tot++] = temp[0], str[tot++] = temp[1], str[tot++] = temp[2];
str[tot] = '\0';
if (strlen(ans) == strlen(str) && strcmp(ans, str) <= 0) {
strcpy(ans, str);
flag = 0;
}
}
}
else if (temp[0] == temp[2]) {
if (num[temp[0] - '0'] > 1 && num[temp[1] - '0']) {
copy(a, num);
a[temp[0] - '0'] -= 2;
a[temp[1] - '0']--;
int tot = 0;
for (int i = 0; i < 10; i++) {
while (a[i] > 0) {
str[tot++] = char(i + '0');
a[i]--;
}
}
str[tot] = '\0';
sort(str, str + tot, cmp);
str[tot++] = temp[0], str[tot++] = temp[1], str[tot++] = temp[2];
str[tot] = '\0';
if (strlen(ans) == strlen(str) && strcmp(ans, str) <= 0) {
strcpy(ans, str);
flag = 0;
}
}
}
else if (temp[1] == temp[2]) {
if (num[temp[1] - '0'] > 1 && num[temp[0] - '0']) {
copy(a, num);
a[temp[1] - '0'] -= 2;
a[temp[0] - '0'] --;
int tot = 0;
for (int i = 0; i < 10; i++) {
while (a[i] > 0) {
str[tot++] = char(i + '0');
a[i]--;
}
}
str[tot] = '\0';
sort(str, str + tot, cmp);
str[tot++] = temp[0], str[tot++] = temp[1], str[tot++] = temp[2];
str[tot] = '\0';
if (strlen(ans) == strlen(str) && strcmp(ans, str) <= 0) {
strcpy(ans, str);
flag = 0;
}
}
}
else if (num[temp[0] - '0'] && num[temp[1] - '0'] && num[temp[2] - '0']) {
copy(a, num);
a[temp[0] - '0']--, a[temp[1] - '0']--, a[temp[2] - '0']--;
int tot = 0;
for (int i = 0; i < 10; i++) {
while (a[i] > 0) {
str[tot++] = char(i + '0');
a[i]--;
}
}
str[tot] = '\0';
sort(str, str + tot, cmp);
str[tot++] = temp[0], str[tot++] = temp[1], str[tot++] = temp[2];
str[tot] = '\0';
if (strlen(ans) == strlen(str) && strcmp(ans, str) <= 0) {
strcpy(ans, str);
flag = 0;
}
}
}
if (flag)
printf("-1\n");
else
printf("%s\n", ans);
}
}
return 0;
}
上一篇： Shiro 和SSM的整合配置