글 읽기 - c++ 반례 찾습니다.

ani8570 3년 전 0

어지간한 반례는 다 성공한 것 같은데 잘 모르겠네요

#include <algorithm>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std; 

bool compare1(pair<int, int> A, pair<int, int> B) {
	return A.first < B.first;
}
bool compare2(pair<int, int> A, pair<int, int> B) {
	if (A.second == B.second)
		return A.first < B.first;
	else
		return A.second > B.second;
}


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, n;
	unordered_map<int, int> umap;
	cin >> T;
	for(int i=0; i< T; i++) {
		cin >> n;
		umap[n]++;
	}
	double total = 0;
	vector<pair<int, int> > v;
	for (auto i = umap.begin(); i != umap.end(); i++) {
		v.push_back({ i->first, i->second });
		total += i->first * i->second;
	}
	sort(v.begin(), v.end(), compare2);
	int a;
	if (v.size() > 1 && v[0].second == v[1].second)
		a = v[1].first;
	else
		a = v[0].first;
	sort(v.begin(), v.end(), compare1);
	
	if(total >= 0)
		cout << int(total / T + 0.5) << '\n';
	else
		cout << int(total / T - 0.5) << '\n';
	cout << v[v.size() / 2].first << '\n';
	cout << a << '\n';
	cout << v[v.size()-1].first - v[0].first;
	return 0;

}

dldyddlwl 3년 전 1

저희는 unordered map으로 값을 받았습니다. 그렇다면, 중앙값을 구할 때, v의 길이가 원래의 길이와는 다르게 되므로 v에서 중앙값을 구하는 것은 정확하지 않을 수 있습니다.

반례는 다음과 같습니다!

EX) 10

=> 글쓴이님의 중앙값) 3

실제 중앙값 ) 2

cout << v[v.size() / 2].first << '\n';



// 아래와 같이 하니 바로 해결!
vector<int> temp;
for(int i=0; i< T; i++) {
	cin >> n;
	umap[n]++;
    temp.push_back(n);
}
cout << temp[temp.size()/2] << '\n';

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

문제

문제

출처

ICPC

c++ 반례 찾습니다.

ani8570 3년 전 0

dldyddlwl 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말