ABC036_C
連想配列mapを使う問題
map
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; }
で値を参照する必要がある.