結果

問題 No.21 平均の差
ユーザー 14番
提出日時 2016-04-03 01:08:52
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,610 bytes
コンパイル時間 1,749 ms
コンパイル使用メモリ 106,880 KB
実行使用メモリ 28,160 KB
最終ジャッジ日時 2024-10-02 12:32:28
合計ジャッジ時間 9,415 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Text;
class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;

        int numCount = int.Parse(Reader.ReadLine());
        this.GroupCount = int.Parse(Reader.ReadLine());

        for (int i = 0; i < numCount; i++)
        {
            this.NumList.Add(int.Parse(Reader.ReadLine()));
        }
        List<int>[] tmp = new List<int>[GroupCount];
        for (int i = 0; i < GroupCount; i++)
        {
            tmp[i] = new List<int>();
        }
        double ans = this.GetAns(0, tmp);
        Console.WriteLine(((int)ans).ToString());

    }


    private int GroupCount = 0;
    List<int> NumList = new List<int>();

    private double GetAns(int idx, List<int>[] grp)
    {
        if (idx == NumList.Count)
        {
            double min = double.MaxValue;
            double max = double.MinValue;
            for (int i = 0; i < GroupCount; i++)
            {
                if (grp[i].Count == 0)
                {
                    return -1;
                }
                else
                {
                    double total = 0;
                    for (int j = 0; j < grp[i].Count; j++)
                    {
                        total += grp[i][j];
                    }
                    total = total / grp[i].Count;
                    min = Math.Min(min, total);
                    max = Math.Max(max, total);
                }
            }
            return Math.Ceiling(max - min);
        }
        else
        {
            double ans = -1;
            int maxElement = NumList.Count - (grp.Length - 1);
            for (int i = 0; i < GroupCount; i++)
            {
                if (grp[i].Count < maxElement)
                {
                    List<int>[] subList = new List<int>[GroupCount];
                    for (int j = 0; j < GroupCount; j++)
                    {
                        List<int> subGruup = new List<int>();
                        subGruup.AddRange(grp[j]);
                        subList[j] = subGruup;
                    }
                    subList[i].Add(this.NumList[idx]);
                    double ret = this.GetAns(idx + 1, subList);
                    if (ret >= 0)
                    {
                        ans = Math.Max(ans, ret);
                    }
                }
            }
            return ans;

        }
    }

    


    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"
 
9
9
1000
1000
1000
1000
1000
1000
1000
1000
1000



 
";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        public static int[] GetInt(char delimiter = ' ', bool trim = false)
        {
            string inptStr = ReadLine();
            if (trim)
            {
                inptStr = inptStr.Trim();
            }
            string[] inpt = inptStr.Split(delimiter);
            int[] ret = new int[inpt.Length];
            for (int i = 0; i < inpt.Length; i++)
            {
                ret[i] = int.Parse(inpt[i]);
            }
            return ret;
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0