Round #690 C.Unique Number(搜索)
原題鏈接
題目大意：
給定一個正整數x，找出一個最小的正整數n，使n的各位數之和等于x，且n的各位不相等，
輸入格式：
第一行一個t(1<= t <= 50)，為t組測驗，
其后每組測驗包括一個正整數x(1<= x <= 50)，
輸出格式：
一行輸出一個答案，共t行，
若n存在，則輸出n，
若不存在，則輸出-1，
輸入樣例：
4
1
5
15
50
輸出樣例：
1
5
69
-1
@Ivan_Alexander說，大學生要善用搜索，
思路：
題目不難，但是第一次寫的時候愣是沒調通…
考慮搜索，將題目轉化為生成一個沒有重復數字的排列，使各位數字相加等于x，且排列的字典序盡可能小，
顯然我們可以按照從小到大的順序選數，保證一定先找到符合要求的，字典序小的排列，在生成排列的程序中無需考慮0，因為0只會增加長度，不改變值，對答案沒有貢獻，
但直接搜索必定超時，所以考慮優化，
一些優化：
- 1—9相加不會超過45，所以大于45的數直接輸出-1
- 在搜索的程序中，如果找到答案就直接退出，不再進行搜索
- 可行性剪枝1：若答案為m階排列，則m是最小的，使從大到小m個數相加大于x的數，答案是唯一的，所以只需生成m階排列，當然，1 <= m <= 9
- 可行性剪枝2：若答案為m階排列，當前已經生成了n階，如果前n階之和加從大到小(m-n)個數小于x，則無需繼續搜索
Code:
#include <bits/stdc++.h>
using namespace std;
int t, x, sum, vis[15], a[15], bj, n;
int dig[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
void dfs(int step)
{
if(bj == 1)
return;
if(step == n + 1)
{
for(int i = 1; i <= n; i++)
sum += a[i];
if(sum < x)
{
sum = 0;
return;
}
bj = 1;
for(int i = 1; i <= n; i++)
{
printf("%d",a[i]);
a[i] = 0;
}
printf("\n");
sum = 0;
return;
}
for(int i = 1; i < step; i++)
sum += a[i];
for(int i = 0; i < n-step+1; i++)
sum += dig[i];
if(sum < x)
{
sum = 0;
return;
}
sum = 0;
for(int i = 1; i <= 9; i++)
{
if(bj == 1)
return;
if(vis[i] == 0)
{
a[step] = i;
vis[i] = 1;
dfs(step+1);
vis[i] = 0;
}
}
return;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &x);
sum = 0;
bj = 0;
for(int i = 0; i < 15; i++)
{
a[i] = vis[i] = 0;
}
if(x > 45)
{
printf("-1\n");
continue;
}
for(int i = 1; i <= 10; i++)
{
if(bj == 1)
break;
n = i;
for(int j = 0; j < n; j++)
sum += dig[j];
if(sum < x)
{
sum = 0;
continue;
}
dfs(1);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/236626.html
標籤：其他