글 읽기 - n^2 으로 한거같은데 시간초과..

sanha93 3년 전 0

맨처음에 1개 i를 고르고(n)

그 이후 i+1 를 왼쪽피벗, n-1을 오른쪽 피벗으로 구해서,

lp rp 가 만날때까지 반복 (n)

이렇게 해서 n^2 인데

무엇때문에 느려지는걸까요?

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <functional>
#define pp pair<long long, string>
using namespace std;

pp best = make_pair(3000000000,"");
pp mkPair(long long a, long long b, long long c) {
	long long num = abs(a + b + c);
	string s = to_string(a) + " " + to_string(b) + " " + to_string(c);
	if (num < best.first)
		return make_pair(num, s);
	else
		return best;
}

int main() {
	int n;
	cin >> n;
	vector<long long > water(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> water[i];
	}
	sort(water.begin(), water.end());
	for (int i = 0; i < n-1; i++) {
		int lp = i + 1;
		int rp = n - 1;
		while (lp != rp) {
			best = mkPair(water[i], water[lp], water[rp]);
			if (water[i] + water[lp] + water[rp] > 0) {
				rp--;
			}
			else if (water[i] + water[lp] + water[rp] == 0) {
				cout << water[i] << " " << water[lp] << " " << water[rp] << endl;
			}
			else
				lp++;
		}
	}
	cout << best.second;
	

	return 0;
}

/*

*/

sanha93 3년 전 0

string s = to_string(a) + " " + to_string(b) + " " + to_string(c);

이게 문제였습니다.

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

문제

문제

출처

ICPC

n^2 으로 한거같은데 시간초과..

sanha93 3년 전 0

sanha93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말