結果
問題 | No.21 平均の差 |
ユーザー | nullzine |
提出日時 | 2017-01-13 11:36:48 |
言語 | Java21 (openjdk 21) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,320 bytes |
コンパイル時間 | 3,039 ms |
コンパイル使用メモリ | 95,024 KB |
実行使用メモリ | 422,408 KB |
最終ジャッジ日時 | 2024-06-01 07:40:34 |
合計ジャッジ時間 | 16,938 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 192 ms
55,620 KB |
testcase_01 | AC | 535 ms
79,560 KB |
testcase_02 | AC | 1,255 ms
146,068 KB |
testcase_03 | AC | 201 ms
55,632 KB |
testcase_04 | RE | - |
testcase_05 | AC | 197 ms
55,384 KB |
testcase_06 | AC | 198 ms
55,672 KB |
testcase_07 | AC | 1,307 ms
176,100 KB |
testcase_08 | AC | 2,201 ms
422,408 KB |
testcase_09 | TLE | - |
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; import java.util.stream.IntStream; /** * Created by nullzine on 2017/01/12. */ public class Main { public static void main(String[] args){ new Main().run(); } private void run(){ Scanner sc = new Scanner(System.in); int[] data = new int[Integer.parseInt(sc.nextLine())]; int k = Integer.parseInt(sc.nextLine()); for(int i=0;i<data.length;i++){ data[i]=Integer.parseInt(sc.nextLine()); } System.out.println((int)new PermutationExecution(data,k).getResult()); } } class PermutationExecution{ private int[] data; private int k; private double result; public PermutationExecution(int[] data,int k){ this.data=data; this.k=k; result=roundUp(calculation()); } private double roundUp(double num){ return num; /* if(0.0<(1.1%1)){ return (int)(num+1); }else{ return (int)num; } */ } private double calculation(){ String[] permutations = permutation(k,data.length); Result[] avgResult = new Result[permutations.length]; IntStream.range(0,avgResult.length).parallel().forEach(e->avgResult[e]=calcAvgsub(permutations[e])); double ret = Double.MIN_VALUE; for(Result result:avgResult){ //System.out.println(result); if(ret<result.maxAvarage-result.minAvarage){ ret=result.maxAvarage-result.minAvarage; } } return ret; } private Result calcAvgsub(String pattern){ NumberGroup[] numberGroups = new NumberGroup[k]; for(int i=0;i<numberGroups.length;i++){ numberGroups[i] = new NumberGroup(); } for(int i=0;i<pattern.length();i++){ numberGroups[Integer.parseInt(pattern.charAt(i)+"")].add(data[i]); } double maxAvg = Double.MIN_VALUE; double minAvg = Double.MAX_VALUE; for(NumberGroup ng:numberGroups){ if(ng.isEmpty()){ return new Result(0,0,"none",numberGroups); } if(maxAvg<ng.getAvarage()){ maxAvg=ng.getAvarage(); } if(ng.getAvarage()<minAvg){ minAvg=ng.getAvarage(); } } return new Result(maxAvg,minAvg,pattern,numberGroups); } private String[] permutation(int a,int b){ String[] ret = new String[(int)Math.pow(a,b)/2]; IntStream.range(0,ret.length).parallel().forEach(e->ret[e]=genPattern(a,b,e)); return ret; } private String genPattern(int a,int b,int c){ String ret = ""; while(c!=0){ ret=(c%a)+ret; c/=a; } return complementStr(ret,b); } private String complementStr(String str,int limit){ for(int i=str.length();i<limit;i++){ str="0"+str; } return str; } public double getResult(){ return result; } } class Result{ public double maxAvarage; public double minAvarage; private String pattern; private NumberGroup[] ngs; public Result(double maxAvarage,double minAvarage,String pattern,NumberGroup[] ngs){ this.maxAvarage=maxAvarage; this.minAvarage=minAvarage; this.pattern=pattern; this.ngs=ngs; } public String toString(){ StringBuilder sb = new StringBuilder(); for(NumberGroup ng:ngs){ sb.append(ng); } return pattern+" "+maxAvarage+" "+minAvarage+" "+sb.toString(); } } class NumberGroup{ private ArrayList<Integer> list; public NumberGroup(){ list = new ArrayList<>(); } public void add(int n){ list.add(n); } public boolean isEmpty(){ return list.isEmpty(); } public double getAvarage(){ double ret = 0.0; for(int n:list){ ret+=n; } return ret/list.size(); } public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("{"); for (int n:list){ sb.append(n+","); } sb.append("}"); return sb.toString(); } }