ABC-61 C big Array を解いてみた
昨日は60-Cを解いたので今日は61-Cを解いて行きました
60-Cよりも考えることが多く結構身になった感じがしました。
以下問題
問題文
空の配列が 1つあります。
この配列に、整数を配列に挿入する操作を N 回行います。 i (1≦i≦N) 回目の操作では、配列に整数 aiを bi 個挿入します。 N 回の挿入操作後の配列の中で、K 番目に小さい数を求めてください。
例えば、配列が
{1,2,2,3,3,3} の時、4 番目に小さい数は 3となります。
制約
- 1≦N≦105
- 1≦ai,bi≦105
- 1≦K≦b1…+…bn
- 入力は全て整数である。
こんな感じ。
おそらくこの問題文のまま実装するとメモリエラー&時間が足りないと言うことになると思います。 (入力のたびにメモリを確保して配列を作り直すのは1024KBを超えてしまう & 作り直した配列をソートの仕方にもよるが、TLEになりかねない？)
考えたこと
まず、問題文のまま実装するとエラーになるので、ハッシュ法風に実装すれば良いのでは？と考えました。
| index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| factor | 2 | 4 | 5 | 6 |
のように0は2個 1は4個....のようにindexはfactor個とデータ構造を構築すれば良いと思います。
次にフローになります
- N,K入力を受け取りそのデータから初期化を行う
- ai bi入力を受け取りながら上記のデータ構造を構築して行く
- そのデータ構造にアクセスする
- indexのfactorが、Kよりも大きい場合にそれを答えとし、データを保持する
- その答えを出力する
と言うもの
コードになります
#include <iostream> #include <vector> using namespace std; int main(void){ long long N,K,ans; cin >> N >> K; vector<long long> container(N); // init for (long long i = 0; i < 100000;i++){ container[i] = 0; } ans = 0; for (long long i = 0; i < N; i++){ long long ai,bi; cin >> ai >> bi; if (ai >= 1 && ai <= 100000 && bi >= 1 && bi <= 100000){ container[ai] += bi; } } for (long long i = 0;i < 100000; i++){ if(0 < K - container[i]){ ans = i + 1; } K -= container[i]; } cout << ans << endl; return 0; }
