結果
問題 |
No.21 平均の差
|
ユーザー |
|
提出日時 | 2017-01-13 11:36:48 |
言語 | Java (openjdk 23) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,320 bytes |
コンパイル時間 | 3,241 ms |
コンパイル使用メモリ | 90,380 KB |
実行使用メモリ | 720,060 KB |
最終ジャッジ日時 | 2024-12-21 12:00:12 |
合計ジャッジ時間 | 17,950 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 RE * 1 MLE * 1 |
ソースコード
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(); } }