문제 URL : https://www.acmicpc.net/problem/20551
20551번: Sort 마스터 배지훈의 후계자
지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제
www.acmicpc.net
문제 접근법 :
- 문제 그대로 구현하시면 됩니다. a배열을 정렬한후 b라는 배열이 되면질문 m이 존재하는지 확인합니다.
- 이분탐색으로 확인하면 빠르겠죠? 그치만 그의 최소 인덱스를 구하기위해선
- 가장 적합한 lower_bound를 사용하면 끝입니다. lower_bound는 해당값의 이상값의 인덱스를 반환하기때문에
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> v1, v2;
void input() {
cin >> n >> m;
v1.resize(n);
v2.resize(m);
for (int i = 0; i < n; i++)
cin >> v1[i];
for (int i = 0; i < m; i++)
cin >> v2[i];
}
void solve() {
sort(v1.begin(), v1.end());
for (int i = 0; i < m; i++) {
int res = lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin();
if (res == n)
cout << -1 << "\n";
else
cout << (v1[res] == v2[i] ? res : -1) << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
return 0;
}
|
cs |
궁금한저 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 5582 공통 부분 문자열 (0) | 2021.07.05 |
|---|---|
| 백준 2531 회전 초밥 (0) | 2021.07.02 |
| 백준 1485 정사각형 (2) | 2021.07.02 |
| 백준 1331 나이트 투어 (0) | 2021.07.02 |
| 백준 2616 소형기관차 (0) | 2021.06.28 |
