読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

ABC036_C

連想配列mapを使う問題
map M;
M[key] = value;
とし, keyを与えられた数値にvalueをその数値が何番目に大きいのかを記録

TLE解法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,x;
    set<int>  s;
    int a[MAX_N],b[MAX_N];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s.insert(a[i]); 
    }
    //setは標準でソートされている
    int value = 0;
    for(set<int>::iterator itr = s.begin();itr!=s.end();itr++){
        int key = *itr;
        for(int i=0;i<n;i++){
            if(a[i]==key){
                b[i]=value;
            }
        }
        value++;
    }
    for(int i=0;i<n;i++){
        cout<<b[i]<<endl;
    }
    return 0;
}

AC解法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int a[MAX_N];
    set<int> S;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        S.insert(a[i]);
    }
    map<int,int>M;
    int value = 0;
    for(set<int>::iterator itr=S.begin();itr!=S.end();itr++){
        M[*itr] = value++;
    }
    for(int i=0;i<n;i++){
        cout<<M[a[i]]<<endl;
    }
    return 0;
}


setについて
set の内部構造は配列ではなく、二分木になっているので、 演算子(operator(size_t))で、指定番目の要素を取り出すことは出来ない。
したがって、イテレータ を使って各要素にアクセスする必要がある。
C++ 順序付集合 std::set 入門

for(set<int>::iterator itr=S.begin();itr!=S.end();itr++){
    cout<<*itr<<endl;
}

で値を参照する必要がある.