百駿1015草
3837 ワード
リンクテキスト
最初は入力したAを並べ替えるだけで、Pの並べ替えの値をインデックスに変換して、簡単に解きました.
もちろん間違っています.
どこに問題があるのか考えてみましたが、コアはA[i]=B[j],j=P[i]でした.
問題の例で言えば.
2 3 1を入力すると、1 2 3にソートされます.A->Bでソートすると、インデックスの変化は0-12から2.01に変わります.なお、Bのみを基準として、1 2 3に対するインデックスは0 1 2である.このインデックス値はP配列と同じです.
よくわかりません.
A[i] = B[P[i]].
ここで並べ替えたAの(値,インデックス)対は(1,2)(2,0)(3,1),Bは(1,0)(2,1)(3,2)である.
値段が1,2,3だと,条件が満たされる.答えはここにある.
Aのインデックスは、P配列の値を決定することができる.
したがって(ソートされたAのインデックス、Bのインデックス(P配列の値)がペアでソートされると、私たちが探しているP配列が現れます.(i=0の場合、A[0]=2,B[?]ga 2になるために?1のはずです.すなわち、P[0]=1である.
(2,0)(0,1)(1,2)対が現れ,対の先頭はPのインデックスであり,後はP配列の値である.
ソート後は(0,1)(1,2)(2,0),P配列の値は120である.
最初は入力したAを並べ替えるだけで、Pの並べ替えの値をインデックスに変換して、簡単に解きました.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i] == arr1[j] && arr[j] != -1) {
arr[j] = -1;
p[j] = i;
}
}
}
では、正解があるわけがないでしょう.もちろん間違っています.
どこに問題があるのか考えてみましたが、コアはA[i]=B[j],j=P[i]でした.
問題の例で言えば.
2 3 1を入力すると、1 2 3にソートされます.A->Bでソートすると、インデックスの変化は0-12から2.01に変わります.なお、Bのみを基準として、1 2 3に対するインデックスは0 1 2である.このインデックス値はP配列と同じです.
よくわかりません.
A[i] = B[P[i]].
ここで並べ替えたAの(値,インデックス)対は(1,2)(2,0)(3,1),Bは(1,0)(2,1)(3,2)である.
値段が1,2,3だと,条件が満たされる.答えはここにある.
Aのインデックスは、P配列の値を決定することができる.
したがって(ソートされたAのインデックス、Bのインデックス(P配列の値)がペアでソートされると、私たちが探しているP配列が現れます.(i=0の場合、A[0]=2,B[?]ga 2になるために?1のはずです.すなわち、P[0]=1である.
(2,0)(0,1)(1,2)対が現れ,対の先頭はPのインデックスであり,後はP配列の値である.
ソート後は(0,1)(1,2)(2,0),P配列の値は120である.
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;
int main() {
int answer = 0;
int n;
int arr[50];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int arr1[50];
\
copy(arr, arr + n, arr1); //A
sort(arr, arr+n); //B
int p[50];
vector<pair<int,int>> v;
for (int i = 0; i < n; i++) {
pair<int, int> p = make_pair(arr1[i], i);
v.push_back(p);
}
sort(v.begin(), v.end());
vector<pair<int, int>> B;
for (int i = 0; i < n; i++) {
pair<int, int> p = make_pair(v[i].second, i);
B.push_back(p);
}
sort(B.begin(), B.end());
for (int i = 0; i < n; i++) {
cout << B[i].second << ' ';
}
}
Reference
この問題について(百駿1015草), 我々は、より多くの情報をここで見つけました https://velog.io/@estry/백준-1015-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol