#271195 (C++11) No.67 よくある棒を切る問題 (1)

• 問題: No.67 よくある棒を切る問題 (1)
• ユーザー: Ktakuya
• 提出日時: 2018-07-07 20:43:02
• 言語: C++11 (gcc 11.4.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 1,068 bytes
• コンパイル時間: 651 ms
• コンパイル使用メモリ: 62,304 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-04-23 19:33:59
• 合計ジャッジ時間: 4,705 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	104 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	69 ms; 5,376 KB
testcase_05	AC	69 ms; 5,376 KB
testcase_06	AC	69 ms; 5,376 KB
testcase_07	AC	93 ms; 5,376 KB
testcase_08	AC	93 ms; 5,376 KB
testcase_09	AC	92 ms; 5,376 KB
testcase_10	AC	63 ms; 5,376 KB
testcase_11	AC	66 ms; 5,376 KB
testcase_12	AC	61 ms; 5,376 KB
testcase_13	AC	85 ms; 5,376 KB
testcase_14	AC	88 ms; 5,376 KB
testcase_15	AC	79 ms; 5,376 KB
testcase_16	AC	70 ms; 5,376 KB
testcase_17	AC	70 ms; 5,376 KB
testcase_18	AC	73 ms; 5,376 KB
testcase_19	AC	94 ms; 5,376 KB
testcase_20	AC	97 ms; 5,376 KB
testcase_21	AC	96 ms; 5,376 KB
testcase_22	AC	66 ms; 5,376 KB
testcase_23	AC	69 ms; 5,376 KB
testcase_24	AC	1 ms; 5,376 KB
testcase_25	AC	4 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	16 ms; 5,376 KB
testcase_29	AC	9 ms; 5,376 KB
testcase_30	AC	4 ms; 5,376 KB

ソースコード

#include <iostream>
#include <iomanip>

typedef long long int Int;
const Int MAX_INT = 1000000000;
const double EPS = 1e-9;

Int min(Int L[], Int N) {
	Int min_val = MAX_INT;
	for (Int i=0; i<N; i++) {
		if (min_val > L[i]) min_val = L[i];
	}
	return min_val;
}

Int sum(Int L[], Int N) {
	Int sum_val = 0;
	for (Int i=0; i<N; i++) sum_val += L[i];
	return sum_val;
}

bool retrievable(double x, Int L[], Int N, Int K) {
	Int max_num = 0;
	for (Int i=0; i<N; i++) {
		max_num += (Int)(L[i] / x);
	}
	return max_num >= K;
}

double find(double a, double b, Int L[], Int N, Int K) {
	if ((b - a) / a < EPS) {
		return a;
	} else {
		double c = (a + b) / 2;
		if (retrievable(c, L, N, K)) {
			return find(c, b, L, N, K);
		} else {
			return find(a, c, L, N, K);
		}
	}
}

int main() {
	Int N;
	std::cin >> N;
	Int L[N];
	for (Int i=0; i<N; i++)
		std::cin >> L[i];
	Int K;
	std::cin >> K;
	
	double a = (double)min(L, N) / (double)K;
	double b = (double)sum(L, N) / (K-0.1) ;
	
	std::cout << std::setprecision(10)
			<< find(a, b, L, N, K) << std::endl;
	
	return 0;
}