글 읽기 - Quick selection으로 풀었는데 시간 초과가 나와요 ㅠㅠ

97mjh1012 5년 전 0

이 문제는 Quick selection으로는 못 푸나요....? 특정 위치의 원소만 찾을때는 이게 제일 빠르다고 들었는데.. ㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> arr;
int start_loc, end_loc, obj_loc, n, m, imsi;

int quickselection(int start_loc, int end_loc, int obj_loc) {
	vector<int> str;
	for (int i = start_loc; i <= end_loc; i++) {
		int temp = arr[i];
		str.push_back(temp);
	}
	nth_element(str.begin(), str.begin() + obj_loc, str.end());

	return str[obj_loc - 1];
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> imsi;
		arr.push_back(imsi);
	}

	for (int i = 0; i < m; i++) {
		cin >> start_loc >> end_loc >> obj_loc;
		cout << quickselection(start_loc - 1, end_loc - 1, obj_loc) << '\n';
	}
	return 0;
}

chogahui05 5년 전 1

네..^^;; Quick select가 O(원소갯수)일 거구.. 평균적으로

10만 * 5000 아닌가요? 시간 초과 날 거 같은데용..^^;;

djm03178 5년 전 0

하나의 쿼리를 수행한다면 quick selection이 평균적으로 제일 빠르겠지만, m개의 쿼리를 수행해야 하는 상황에서는 더 좋은 방법이 있습니다.

사실 상당히 어려운 문제입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Quick selection으로 풀었는데 시간 초과가 나와요 ㅠㅠ

97mjh1012 5년 전 0

chogahui05 5년 전 1

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말