글 읽기 - windows 기법을 수정을 했으나 시간 초과

cg456456 4년 전 0

음 전의 대답을 바탕으로 탐욕법 대신 windows 기법으로 해서 수정 했는데 시간 초과가 뜨네요 혹시 어디서 뜨는지 알수 있는지 가르쳐주시면 감사하겟습니다

#include<iostream>
#include<deque>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXM = 987654321;
deque<int > dq;
//deque<int> num;
//long long int x[MAX];
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int K;

	int temp;
	long long int m = MAXM; long long int M = 0;
	long long int result = MAXM;
	cin >> N >> K; // N과 K를 받는다

	for (int i = 0; i < N; i++)
	{
		cin >> temp; // 받은 수열들을 차례로 넣는다
		dq.push_back(temp);
		//cout << dq.back() << endl;
	}
	sort(dq.begin(), dq.end()); // 오름차순으로 분류 

	K = N - K; // N-K 만큼 돌려야 하므로 ex) 5 3 일때 4번 돌려야 하므로 5-3 =2
	for (int i = 0; i <= N - K; i++) // windows 기법으로 N-K만큼 만 본다
	{
		for (int j = i; j < i + K; j++)
		{
            // if 문으로 최솟값을 찾는다 혹시 여기에서 시간 초과가 나는 것인지?
			temp = dq[j + 1] - dq[j]; //cout <<temp << endl;
			if (temp < m) {
				m = temp;
			}
		}
		M = dq[K + i-1] - dq[i]; // 최댓값 구하기
		//cout << result << endl;
		result = min(result, m + M); // 전의 값과 비교하여 작은거 찾기
		m = MAXM; // 최솟값을 초기화
	}
	cout << result <<"\n";
}

adh0463 4년 전 1

짜신 소스로 봤을 때, 최악의 경우 N=1000000, K = 1일 때 시간 초과가 나네요.

현재 단계에서 가지고 있는 window에서 다음 단계로 넘어갈 때, 다음 단계에서 불필요한 부분만을 제거하고, 다음 단계에서 window에 포함되는 부분을 추가하는 방식입니다. 님이 짜신 소스는 for문을 하나 더 씀으로써 '현재 단계에 있는 window'를 재활용하지 못하고 있네요

요약하면 이중 for문이 문젭니다.

cg456456 4년 전 0

감사합니다 한번 for 문 안쓰고 최솟값 찾는 경우를 생각해야 될거 같군요

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

문제

문제

출처

ICPC

windows 기법을 수정을 했으나 시간 초과

cg456456 4년 전 0

adh0463 4년 전 1

cg456456 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말