글 읽기 - 더 틀릴게 없는 것 같습니다..

greedy 3년 전 0

게시판에 있는 모든 반례를 통과합니다.

곱이 합보다 큰 경우만을 따로 뽑아내어 내림차순 정렬을 한 후 묶음처리되지 않은 원소들은 개별로 덧셈을 해주었습니다. 문제가 될만한 부분이 있을까요?

#include <bits/stdc++.h>
using namespace std;
struct P {
	int v, x, y;
	bool operator <(const P&rhs)const {
		return v > rhs.v;
	}
};
int N, a[10001], vis[10001];

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];
	sort(a, a + N);
	vector<P> b;
	for (int i = 0; i < N - 1; i++) {
		if (a[i] * a[i + 1] > a[i] + a[i + 1])
			b.push_back({ a[i] * a[i + 1], i, i + 1 });
	}
	sort(b.begin(), b.end());
	int ans = 0, sz = (int)b.size();
	for (int i = 0; i < sz; i++) {
		int l = b[i].x, r = b[i].y;
		assert(0 <= l && l < N && 0 <= r && r < N);
		if (vis[l] || vis[r]) continue;
		ans += b[i].v;
		vis[r] = vis[l] = 1;
	}
	for (int i = 0; i < N; i++) ans += (1 - vis[i]) * a[i];
	cout << ans;

	return 0;
}