AtCoder Beginer Contest 061 C - Big Array
twitterで #いいねされた数だけAtCoderでAC というハッシュタグを使ってしまったので、そのうちの一問です。
ABC061のC問題です。問題名は「Big Array」、空っぽの配列Big Arrayにa[i]という数をb[i]個入れる操作をi=(1→N)について行ったとき、Big ArrayのなかでK番目に小さい数を出力しなさいという問題です。ちなみに、実際に問題通りのBigArrayを作ろうとすると、恐らくMLEになります。
#include <iostream> #define a_MAX 100000 using namespace std; long long ary[a_MAX+1]; int main(void){ int N; long long K; cin >> N >> K; int a, b; for(int i=0; i<N; i++){ cin >> a >> b; ary[a] += b; } long long ans = 0; for(int i=1; ans<K && i<=a_MAX; i++){ ans += ary[i]; if(ans>=K){ cout << i << '\n'; break; } } return 0; }
ary[i]に、Big Arrayのなかにiという数が何個含まれているかを記憶します。そんで、aryの中身を小さい順にansに足してって、ansがちょうどK以上になるようなiの値を出力してやれば、K番目に小さな値を出力したことになります。
んで、こっからは技術的な何か
#defineっていうのは、マクロ処理ってやつで、#define a b とやると、ソースコード内のaという"文字列"をすべてbという"文字列"に置き換えてコンパイルしてくれます。便利な使い方として、
#include <iostream> #define f(a,b) a+b int main(){ int sum = f(3,4); cout << sum << endl; }
などとすると、 f(3,4)という文字列を3+4という文字列に変換してコンパイルしてくれるので、上のコードだと7が出力されます。
便利ですが、2人以上の人数で開発を行うときは、絶対に使わないようにしてください。バグと宗教戦争のもとです。
では、ばいばい。