문제요약:
N개의 pair sequence (ai,bi)가 들어온다.
그 중에 M개를 골라서 ai를 더하고 S개를 골라서 bi를 더할때 최댓값은?
오픈채팅에서 올라온 문제였는데, 재밌어보여서 풀었습니다.
처음에 접근 방식을 약간 수정해서 맞았는데, 그리디 + pq로 해결했습니다.
집합 a를 ai를 더하는 원소의 index, b를 bi를 더하는 원소의 index 이라고 정의합시다.
그렇다면, 어떤 집합 a를 고르던지, b는 고정이 됩니다.
즉 집합 a가 정해지면, a에 포함되지 않은 원소들 중 bi값이 큰 S개를 뽑은게 b가 되는게 항상 최적입니다.
그렇다면 다음과 같은 전략을 생각해볼 수 있습니다.
1. 우선 ai값이 가장 큰 M개를 a로, 그리고 남은 것들 중 bi값이 큰 S개를 b로 하는것을 초기상태로 둔다.
2. 초기상태에서 a의 원소 하나를 교체해 가면서 그때그때 최적의 값을 갱신해나갑시다.
그럼 생각해 볼것이, 어떤 i는 다음 3가지 상태중에 하나에 포함됩니다.
1. i는 a에 들어간다.
2. i는 b에 들어간다.
3. 나머지 경우
그럼 여기서 하나 그리디한 성질이 성립하는데요, a에의 원소중 하나를 교체할건데, 1번 경우에서 2번 경우로 보내는 경우만 판단해주면 됩니다. 그럼 bi-ai가 가장 큰 원소 하나가 빠져야 겠죠? 여기서 pq를 사용하시면 됩니다.
그리고 a가 하나 빠졌고, b가 하나 늘은 상태인데, a에 추가해줄 원소는 고정되어 있습니다. a가 큰 순서대로 하나씩 넣으시면 됩니다.
즉 어떤 느낌이냐면, 처음에 a는 ai가 가장 큰 m개라면, 그 다음 교환 차례일때 bi-ai가 가장 큰 a의 원소를 하나 빼고, m+1째로 ai 가 큰 i를 a에 넣는다.
그런데 a에 새로 포함시키는 원소가 이미 2번 경우였다면 그냥 교환해주면 되고, 만약 3번이었다면, b에서 원소를 하나 빼줘야 하는데, 이는 b의 원소중 bi가 가장 작은 한개를 빼주면 됩니다. 이도 pq로 구현해주면 됩니다.
뭔가 말로만 하면 어려운데 코드도 첨부합니다. +구현도 쉽지 않은 어려운 문제인듯.
#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
//written by djs100201
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 100, inf = 1e18, mod = 998244353, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base = 1, ans, t_c;
ll gcd(ll x, ll y) {
if (!y)return x;
return gcd(y, x % y);
}
ll checked[n_];
bool cmp(P a, P b) {
if (a.first != b.first)return a.first > b.first;
return a.second < b.second;
}
void solve() {
cin >> n >> x >> y;
vector<P>v(n), A;
priority_queue<P>pq;
priority_queue<P, vector<P>, greater<>>pq2;
for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
sort(all(v),cmp);
for (int i = 0; i < n; i++)checked[i] = 1, sum += v[i].second;
for (int i = 0; i < x; i++)pq.push({ v[i].second - v[i].first ,i }), sum += v[i].first - v[i].second, checked[i] = 0;
for (int i = x; i < n; i++)pq2.push({ v[i].second,i });
z = pq2.size();
for (int i = 0; i <z- y; i++)sum -= pq2.top().first, checked[pq2.top().second] = 0, pq2.pop();
ans = sum;
for (int i = x; i < n; i++) {
if (!x || !y)break;
auto a = pq.top();
pq.pop();
sum += a.first;
pq2.push({ v[a.second].second, a.second });
checked[a.second] = true;
if (checked[i]) {
checked[i] = 0;
pq.push({ v[i].second - v[i].first,i });
sum += v[i].first - v[i].second;
}
else {
sum += v[i].first;
pq.push({ v[i].second - v[i].first,i });
while (pq2.size() && !checked[pq2.top().second])pq2.pop();
if (pq2.size()) {
auto b = pq2.top();
sum -= b.first;
checked[b.second] = 0;
pq2.pop();
}
}
ans = max(ans, sum);
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
//cin >> tc;
while (tc--)solve();
}
checked라는 변수는 현재 이 index가 집합 b에 포함되는지 여부입니다.