UVa 13031 - Geek Power Inc.

Source

An Asian Preliminary Regional（20151205）
(ICPC Dhaka 2015 Preliminary)
UVa 13031

問題概要

電源があり，各電源には効率が定められており，その効率と同じだけの電気を作ることができる．
電源を複数使うことができるが，複数使った場合は，最も低い効率に合わせられ，全ての電源がその効率と同じだけの電気を作る．
今 $N$ 種類の電源があり，電源 $i$ は $K_i$ 個持っており，効率は $P_i$ である．
最もたくさんの電気を作りたい時，いくら作れるかを求める問題．

• テストケースの数 $T$ は $T \leq 200$ を満たす
• $1 \leq N \leq 50$
• $1 \leq K_i \leq 100000\ (10^5)$
• $1 \leq P_i \leq 1000\ (10^3)$

解法

使う電源の最小効率を決めたら，それ以上の効率の電源は全て使うのが最適．
効率の値でソートしておき，効率がが大きい方から順番でそこまで使うとして，使える電源の数も同時に求めていけば良い．
時間計算量は $O(N \log N)$．

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります．

Current time: 2024年04月19日09時51分27秒
Last modified: 2015年12月16日01時21分56秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る

Logged in as: unknown user (not login)