結果
問題 | No.210 探し物はどこですか? |
ユーザー |
![]() |
提出日時 | 2015-05-16 00:05:10 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 377 ms / 2,000 ms |
コード長 | 5,378 bytes |
コンパイル時間 | 1,253 ms |
コンパイル使用メモリ | 110,976 KB |
実行使用メモリ | 20,480 KB |
最終ジャッジ日時 | 2024-07-06 04:37:06 |
合計ジャッジ時間 | 16,006 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.IO;using System.Collections.Generic;using System.Globalization;using System.Linq;using System.Text;public class PriorityQueue<T> {private T[] array = new T[100];private int size = 0;private Comparison<T> comp;public PriorityQueue() {this.comp = Comparer<T>.Default.Compare;}public PriorityQueue(Comparison<T> comp) {this.comp = comp;}private void Swap(int a, int b) {T t = array[a];array[a] = array[b];array[b] = t;}private void Expand() {var newlist = new T[array.Length * 2];Array.Copy(array, newlist, array.Length);array = newlist;}public bool Any() {return size > 0;}public void Enqueue(T newValue) {if (size >= array.Length) {Expand();}array[size++] = newValue;int pos = size - 1;while (pos > 0) {int parent = (pos - 1) / 2;if (comp(array[parent], array[pos]) > 0) {Swap(parent, pos);pos = parent;} elsebreak;}}public T Dequeue() {T top = array[0];array[0] = array[--size];int pos = 0;while (pos * 2 + 1 < size) {int left = pos * 2 + 1;int right = left + 1;int next = left;if (right < size && comp(array[left], array[right]) > 0)next = right;if (comp(array[pos], array[next]) > 0) {Swap(next, pos);pos = next;} elsebreak;}return top;}};public struct Node {public double Percentage { get; set; }public int Room { get; set; }}partial class Solver {public void Run() {var n = ni();var p = ni(n);var q = ni(n);// メガネがその部屋にある確率var percentage = p.Select(x => x / 1000.0).ToArray();// 見つかる確率var find = q.Select(x => x / 100.0).ToArray();var qu = new PriorityQueue<Node>((n1, n2) => -n1.Percentage.CompareTo(n2.Percentage));double ans = 0;for (int i = 0; i < n; i++) {qu.Enqueue(new Node { Percentage = percentage[i] * find[i], Room = i });}for (int i = 1; i < 1000000; i++) {var node = qu.Dequeue();ans += i * node.Percentage;node.Percentage *= (1.0 - find[node.Room]);qu.Enqueue(node);}cout.WriteLine("{0:F10}", ans);}}// PREWRITEN CODE BEGINS FROM HEREpartial class Solver : Scanner {public static void Main(string[] args) {/*new Solver("1 1000 50", Console.Out).Run();new Solver(@"10100 100 100 100 100 100 100 100 100 100100 100 100 100 100 100 100 100 100 100", Console.Out).Run();new Solver(@"1064 201 4 30 232 64 197 7 102 9928 43 94 52 24 33 97 55 36 89", Console.Out).Run();*/new Solver(Console.In, Console.Out).Run();}TextReader cin;TextWriter cout;public Solver(TextReader reader, TextWriter writer): base(reader) {this.cin = reader;this.cout = writer;}public Solver(string input, TextWriter writer): this(new StringReader(input), writer) {}public int ni() { return NextInt(); }public int[] ni(int n) { return NextIntArray(n); }public long nl() { return NextLong(); }public long[] nl(int n) { return NextLongArray(n); }public string ns() { return Next(); }}public class Scanner {private TextReader Reader;private Queue<String> TokenQueue = new Queue<string>();private CultureInfo ci = CultureInfo.InvariantCulture;public Scanner(): this(Console.In) {}public Scanner(TextReader reader) {this.Reader = reader;}public int NextInt() { return Int32.Parse(Next(), ci); }public long NextLong() { return Int64.Parse(Next(), ci); }public double NextDouble() { return double.Parse(Next(), ci); }public string[] NextArray(int size) {var array = new string[size];for (int i = 0; i < size; i++) array[i] = Next();return array;}public int[] NextIntArray(int size) {var array = new int[size];for (int i = 0; i < size; i++) array[i] = NextInt();return array;}public long[] NextLongArray(int size) {var array = new long[size];for (int i = 0; i < size; i++) array[i] = NextLong();return array;}public String Next() {if (TokenQueue.Count == 0) {if (!StockTokens()) throw new InvalidOperationException();}return TokenQueue.Dequeue();}public bool HasNext() {if (TokenQueue.Count > 0)return true;return StockTokens();}private bool StockTokens() {while (true) {var line = Reader.ReadLine();if (line == null) return false;var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);if (tokens.Length == 0) continue;foreach (var token in tokens)TokenQueue.Enqueue(token);return true;}}}