백준 BOJ 11003 - 최솟값 찾기

역대급으로 어이없는 문제.....

 

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

priority_queue와 fastio의 조합이라는

말도안되는 정답을 요구한다

 

printf / scanf -> TLE

cout / cin with fastio -> AC

????????

 

맞춰놓긴 했는데

왜이런진 아직도 모르겠다.

 

인덱스를 저장해두고 최솟값을 꺼낼때

인덱스 범위를 충족하는지 확인해주면 되는 문제였다.

아마 이런거 보면 이게 꼼수쯤 되는 풀이인거 같긴 한데....

아몰랑 맞왜틀 엄청 한 문제였다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

priority_queue<pii, vector<pii>, greater<pii>> pq;

int main(){
	int n,l,k;
	scanf("%d %d", &n, &l);
	for(int i=0; i<n; i++){
		scanf("%d", &k);
		pq.push({k,i});
		
		while(i-l+1>=0 && pq.top().second < i-l+1){ pq.pop(); }
		printf("%d ", pq.top().first);
	}
	return 0;
}

TLE 소스

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

priority_queue<pii, vector<pii>, greater<pii>> pq;

int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n,l,k;
	cin >> n >> l;
	for(int i=0; i<n; i++){
		cin >> k;
		pq.push({k,i});
		
		int tmp = i-l+1;
		while(tmp>=0 && pq.top().second < tmp){ pq.pop(); }
		cout << pq.top().first << ' ';
	}
	return 0;
}

AC 소스