結果
問題 | No.50 おもちゃ箱 |
ユーザー |
|
提出日時 | 2014-10-27 01:09:04 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,328 ms / 5,000 ms |
コード長 | 1,461 bytes |
コンパイル時間 | 2,496 ms |
コンパイル使用メモリ | 79,068 KB |
実行使用メモリ | 50,436 KB |
最終ジャッジ日時 | 2024-06-25 20:54:04 |
合計ジャッジ時間 | 49,318 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int toy[]=new int[n]; for(int i=0;i<n;i++){ toy[i]=sc.nextInt(); } int m=sc.nextInt(); int box[]=new int[m]; for(int i=0;i<m;i++){ box[i]=sc.nextInt(); } Arrays.sort(box); int x=1; int y=n; while(y>1){ x*=y; y--; } int ans=100; for(int i=0;i<x;i++){ int p[]=permutation(toy,i,x); boolean used[]=new boolean[m]; int b[]=new int[m]; for(int j=0;j<m;j++){ b[j]=box[j]; } int nokori=n; for(int j=0;j<n;j++){ for(int k=m-1;k>=0;k--){ if(b[k]>=p[j]){ b[k]-=p[j]; used[k]=true; nokori--; break; } } } int ak=0; for(int j=0;j<m;j++){ if(b[j]!=box[j])ak++; } if(nokori==0)ans=Math.min(ans,ak); } if(ans==100)System.out.println(-1); else System.out.println(ans); } static int[] permutation(int[] base, int x,int k) { int n = base.length; int ans[] = new int[n]; if (n == 1) return base; else { ArrayList<Integer> B = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { B.add(base[i]); } k /= n; int N = n - 1; for (int i = 0; i < n - 1; i++) { ans[i] = B.get(x / k); B.remove(x / k); x %= k; k /= N; N--; } ans[n - 1] = B.get(0); } return ans; } }