AcWing 1226. 包子凑数
原题链接
中等
作者:
暂时换个名字
,
2021-01-24 18:35:36
,
所有人可见
,
阅读 404
import java.util.Scanner;
import java.util.Arrays;
class Main{
static int[] jilu;
static final int N=10000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int[] arr = new int[n];
while(n-->0)arr[n]=sc.nextInt();
int result = f(arr);
if(result==-1)System.out.println("INF");
else System.out.println(result);
}
public static boolean shaixuan(int[] arr) {
int flag=0;
for(int i=2;i<=arr[0];i++) {
for(int j=0;j<arr.length;j++) {
if(arr[j]%i==0)flag++;
}
if(flag==arr.length)return false;
flag=0;
}
return true;
}
public static int f(int[] arr) {
if(!shaixuan(arr))return -1;
Arrays.sort(arr);
jilu=new int[arr[arr.length-1]];
int step=0,result=arr[0]-1;
for(int i=arr[0];;i++) {
if(step>=arr[0])break;
if(panduan(arr,i)) {
step++;jilu[(i-1)%arr[arr.length-1]]=1;
}
else{
step=0;result++;
}
}
return result;
}
public static boolean panduan(int[] arr,int index) {
for(int i=0;i<arr.length;i++) {
if(index==arr[i])return true;
if(index>arr[i]&&jilu[(index-1-arr[i])%arr[arr.length-1]]==1)return true;
}
return false;
}
}