変なタイトルですが、こんな問題です。
n 本のパイプがあり、長さはそれぞれ A_1, A_2, …, A_n です。今、n 本のパイプから k 本の同じ長さのパイプを切り出すことを考えます。パイプを切って分割することはできますが、つなげることはできません。
パイプの切り方を工夫した結果、切り出すことができるパイプの長さの最大値を答えてください。
答えは整数になるとは限りません。相対誤差または絶対誤差が 10^-6 (0.000001) 以下であれば正解とみなされます。
パイプを分割する問題
二分探索法でパイプの長さの最大値と最小値を狭めていきます。差が0.000001以下になるまで二分探索を繰り返して解を求めます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] As = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); double left = 0; double right = As.Max(); // right - left > 0.000001 でよいのだが // 念のためright - leftがもっと小さな値になるまで繰り返す while (right - left > 0.00000001) { // mid で実際にn本切り出せるか数えてみる double mid = (left + right) / 2; int count = 0; foreach (int a in As) count += (int)Math.Floor(a / mid); if(count >= K) left = mid; else right = mid; } Console.WriteLine(left); } } |
切れ目で分割する問題
長さ L [cm] の太巻きがあり、これを n 人で分けようとしています。太巻きにはあらかじめ k 個の切れ目が入っており、i 個目の切れ目は左端から A_i [cm] のところに入っています。あなたは、切れ目を n-1 個選んでそこで切ることにより、太巻きを n 分割しようとしています。
切れ目の選び方を工夫したとき、最も短い太巻きの長さを最大でいくつにできるかを答えてください。
解として考えられる最大値は L であり、最小値は0です。そこで left は0、right を L で初期化します。そのあと left と right の中間の値 mid を求め、その長さで太巻きを n 個にわけることができるか調べます。できるのであれば left に mid を代入し、できない場合は right に mid を代入します。これを left と right の差が1以下になるまで繰り返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int L, n, k; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); L = vs[0]; n = vs[1]; k = vs[2]; } List<int> As = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList(); As.Insert(0, 0); As.Add(L); int[] Bs = new int[k + 1]; for (int i = 0; i < k + 1; i++) Bs[i] = As[i + 1] - As[i]; int left = 0; int right = L; while (right - left > 1) { int mid = (left + right) / 2; int count = 0; int len = 0; foreach (int b in Bs) { len += b; if (len >= mid) { len = 0; count++; } } if(count >= n) left = mid; else right = mid; } Console.WriteLine(left); } } |
切れ目で分割する問題（別パターン）
長さ L [cm] の太巻きがあり、これを n 人で分けようとしています。太巻きにはあらかじめ k 個の切れ目が入っており、i 個目の切れ目は左端から A_i [cm] のところに入っています。あなたは、切れ目を n-1 個選んでそこで切ることにより、太巻きを n 分割しようとしています。
切れ目の選び方を工夫したとき、最も長い太巻きの長さを最小でいくつにできるかを答えてください。
前回と似た問題です。前回はもっとも短いものの最大値を求めましたが、今回はもっとも長いものの最小値を求めます。
今度は切り分けた太巻きの長さが mid を超えないようにするのですが、切り分けた太巻きの長さが mid を超えたら単純にcountをインクリメントして次扱いするだけでは不十分です。「切れ目と切れ目のあいだが mid を超えている場合はどうやってもできない」ということを見落とさないようにしなければなりません（これに気づかず誤答を連発してしまった）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int L, n, k; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); L = vs[0]; n = vs[1]; k = vs[2]; } List<int> As = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList(); As.Insert(0, 0); As.Add(L); int[] Bs = new int[k + 1]; for (int i = 0; i < k + 1; i++) Bs[i] = As[i + 1] - As[i]; int left = 0; int right = L + 1; while (right - left > 1) { int mid = (left + right) / 2; int count = 1; int len = 0; bool impossible = false; foreach (int b in Bs) { // count 本目の長さがmidを超えないようにする // 超えてしまったらそれは次の物となる // 【注意！】 b が mid を超える場合はそもそも無理！ if (b > mid) { impossible = true; break; } if (len + b <= mid) len += b; else { len = b; count++; } } // 分割数が n を超えてしまったら失敗 leftを増やす if (impossible || count > n) left = mid; else right = mid; } Console.WriteLine(right); } } |
