글 읽기 - [C++] 반례를 못찾겠습니다.

se1620236 5년 전 0

아무리 찾아봐도 반례가 안나오네요.

도와주십시요.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
	cin.tie(NULL);
    ios_base::sync_with_stdio(0);
	//freopen("input.txt", "r", stdin);

	int n = 0;
	cin >> n;

	vector<pair<long long, long long>> v;
	vector<long long> vx;
	vector<long long> vy;

	v.push_back(make_pair(0, 0));
	vx.push_back(0);
	vy.push_back(0);

	for(int i=0; i<n; i++) {
		long long x = 0, y = 0;
		cin >> x >> y;
		vx.push_back(x);
		vy.push_back(y);
		v.push_back(make_pair(x, y));
	}

	sort(vx.begin()+1, vx.end());
	sort(vy.begin()+1, vy.end());

	vector<long long> vpx = vx;
	vector<long long> vpy = vy;

	for(int i = 1; i <= n; i++) {
		vpx[i] = vpx[i-1] + vpx[i];
	}

	for(int i = 1; i <= n; i++) {
		vpy[i] = vpy[i-1] + vpy[i];
	}

	long long res = 0;
	long long min = numeric_limits<long long>::max();
	for(auto i = v.begin()+1; i != v.end(); i++) {
		auto iterX = find(vx.begin()+1, vx.end(), i->first);
		int idxX = distance(vx.begin(), iterX);
		auto iterY = find(vy.begin()+1, vy.end(), i->second);
		int idxY = distance(vy.begin(), iterY);

		long long tmp_sum = 0;

		tmp_sum += vpx[n-1] - vpx[idxX] - vpx[idxX-1] - (n-idxX)*(i->first) + (idxX-1)*(i->first);
		tmp_sum += vpy[n-1] - vpy[idxY] - vpy[idxY-1] - (n-idxY)*(i->second) + (idxY-1)*(i->second);


		if(tmp_sum < min) {
			min	= tmp_sum;
			res = distance(v.begin(), i);
		}
	}

	cout << res;

	return 0;
}

se1620236 5년 전 0

find() -> lower_bound() 함수로 바꾸니 해결됐습니다.

탐색 속도가 느려서 그랬던거 같은데 왜 시간초과가 아니라 틀렸다고 뜨는지 모르겠네요.

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

문제

문제

출처

ICPC

[C++] 반례를 못찾겠습니다.

se1620236 5년 전 0

se1620236 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말