u_sho競プロぶろぐ

21歳。みゃーくぴとぅ。ゆる~く続けますたぶん。  デザイン変えました(2019/2/25)これでいきます

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人以上の人数で開発を行うときは、絶対に使わないようにしてください。バグと宗教戦争のもとです。

 では、ばいばい。