글 읽기 - 반례 부탁드립니다

dk10211 3년 전 0

대략적인 알고리즘을 설명 드리자면 B가 가져갈 값은 내림차순 정렬(B기준)1~m*2(문제에선 k)중 값으로 한정되어 있으므로

1~m*2범위 안에서는 플레이어 A가 이것을 가져간다면 B에게 그만큼 손해를 준다고 가정하여 A[i]+B[i]를 기준으로 내림차순 정렬을 하여 앞선 1~m개를 가져가게 하고 B가 가져갈 숙련도들은 k라는 우선순위 큐를 만들어서 따로 보관해 두었습니다. 그리고 m*2+1~n까지의 남은 숫자들은 비교를 하며 선택적으로 취하는데 이 선택의 기준은 a(자신이 포기하면 플레이어 B가 바로 가져갈 값들),b(자신이 포기해도 B가 가져가지 않을 값들)로 분류해서 최솟값을 찾고 그것을 최소이득이라 하였을 때 그 이득보다 선택하는 값이 크다면 넣는 식으로 코드를 짰습니다.

혼자서 반례를 찾는 건 너무 힘들 것 같아 부탁 드려봅니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
stack<pair<int, int>>a;
priority_queue<int, vector<int>, greater<int>>b;//f는 data s는  num;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>a_z;
priority_queue<int, vector<int>, greater<int>>k;//플레이어 B가 포기하는 최솟값
bool c[800005];//체크용
bool fc(pair<int, int>& A, pair<int, int>& B) {
	return A.second > B.second;
}
bool cmp(pair<int, int>& A, pair<int, int>& B) {
	if (A.first + A.second == B.first + B.second) {
		return A.first > B.first;
	}
	return A.first + A.second > B.first + B.second;
}
int at() {
	while (1) {
		if (a.empty()) return 2100000000;
		else {
			int x = a.top().second;
			if (c[x])
				return a.top().first;
			else
				a.pop();
		}
	}
}
int bt() {
	if (b.empty()) return 2100000000;
	else return b.top();
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>>v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].first;
	for (int i = 0; i < n; i++)
		cin >> v[i].second;
	sort(v.begin(), v.begin() + n, fc);//B기준 내림차순
	sort(v.begin(), v.begin() + m * 2, cmp);
	/*for (int i = 0; i < n; i++) {
		cout << i + 1 << " : " << v[i].first << " " << v[i].second;
		cout << "\n";
	}*/
	for (int i = m; i < m * 2; i++)
		k.push(v[i].second);
	int kt = k.top();
	for (int i = 0; i < m; i++) {
		if (v[i].second > kt) {
			a.push(make_pair(v[i].first + v[i].second, i));
			a_z.push(make_pair(v[i].second, i));//체크표시 하기 위함(최솟값 증가)
			c[i] = true;
		}
		else {
			b.push(v[i].first);
		}
	}
	//cout << a.size() << " " << b.size() << " " << k.size() << "\n";
	for (int i = m + m; i < n; i++) {
		int A = at();
		int B = bt();
		A -= k.top();
		//cout << A << " " << B << "\n";
		if (A < B) {
			int x = a.top().second;
			if (A <= v[i].first) {
				a.pop();
				c[x] = false;
				k.pop();
				k.push(v[x].second);
				b.push(v[i].first);
				kt = k.top();
				while (!a_z.empty()) {
					//cout << kt << " " << a_z.top().first << "\n";
					if (!c[a_z.top().second]) {
						a_z.pop();
						continue;
					}
					if (a_z.top().first <= kt) {
						int xx = a_z.top().second;
						c[xx] = false;
						b.push(v[xx].first);
						a_z.pop();
					}
					else break;
				}
			}
		}
		else {
			if (B < v[i].first) {
				b.pop();
				b.push(v[i].first);
			}
		}
	}
	long long sum = 0;
	while (!a.empty()) {
		if (!c[a.top().second]) a.pop();
		else {
			sum += (long long)v[a.top().second].first;
			a.pop();
		}
	}
	while (!b.empty()) {
		sum += (long long)b.top();
		//cout << b.top() << "\n";
		b.pop();
	}
	//cout << sum << "\n";
	while (!k.empty()) {
		sum -= (long long)k.top();
		k.pop();
	}
	cout << sum;
}

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

문제

문제

출처

ICPC

반례 부탁드립니다

dk10211 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말