AcWing 1209. 带分数
原题链接
简单
作者:
豪满天下
,
2019-12-04 12:51:11
,
所有人可见
,
阅读 1161
import java.util.Scanner;
public class Main {
//带分数 全排列+筛选
static Scanner in = new Scanner(System.in);
//保存1-10的全排列
static int[] temp = new int[9];
static int[] num = {1,2,3,4,5,6,7,8,9};
static boolean[] visit = new boolean[10];
static int count=0;
static int n;
public static void main(String[] args) {
n = in.nextInt();
dfs(0);
System.out.println(count);
}
private static void dfs(int pos) {
if(pos==temp.length){
if(check(temp,n)){
count++;
}
return;
}
//i是数组的索引
for(int i=0;i<9;i++){
if(visit[i]) continue;
temp[pos] = num[i];
visit[i] =true;
dfs(pos+1);
visit[i] = false;
}
}
private static boolean check(int[] temp,int n) {
//如果能拼凑n 返回true 否则返回false
String num = String.valueOf(n);
float res;
int len = num.length();
for(int i=0;i<len;i++){
int left = getNum(temp,0,i);
if(left>n) break;
int right = 0;
for(int j=i+1;j<temp.length-1;j++){
float up = getNum(temp,i+1,j);
float down = getNum(temp,j+1,temp.length-1);
if(up<down) continue;
res = left+up / down;
if(res == n) {
return true;
}
}
}
return false;
}
static int getNum(int []temp,int start ,int end){
int res = 0;
while(start<=end){
res = res * 10 + temp[start];
start++;
}
return res;
}
}