CF1374E1题解

_Leehom_ · 2024-08-01 19:37:37 · 题解

题意

形式化的来说，你需要找出一个包含一些书的集合，使得集合所包含的书满足 \sum a_i \geq k \land \sum b_i \geq k 并在满足以上条件的情况下使 \sum t_i 最小。

解法

可以使用一种近似于反悔贪心的算法，先给两个人每人塞 k 本只有自己喜欢的书，接下来用一些两个人都喜欢的书去替换两个人各自选的书中 t_i 最大的两本，如果这两本书的 t_i 之和 \geq 这本两个人都喜欢的书了，直接跳过。

如果在给两个人塞书塞完后发现没有塞满 k 本，就需要在加书时特殊判断一下。

维护两个人手里重量最大的书直接使用优先队列维护。

#include <iostream>

#include <algorithm>

#include <queue>

#define endl '\n'

using namespace std;

const int N = 2e5 + 5;

struct Node{
  int t, a, b;
  bool operator<(const Node &i) const {
    return t < i.t;
  }
}p[N];

int n, k, a, b, ans;

priority_queue<int>booka, bookb;

int main(){
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) cin >> p[i].t >> p[i].a >> p[i].b;
  sort(p + 1, p + n + 1);
  for(int i = 1; i <= n && (a < k || b < k); ++i){
    if(p[i].a == 1 && p[i].b == 0 && a < k){
      booka.push(p[i].t);
      a++;
      ans += p[i].t;
    }else if(p[i].b == 1 && p[i].a == 0 && b < k){
      bookb.push(p[i].t);
      b++;
      ans += p[i].t;
    }
  }
  for(int i = 1; i <= n; ++i){
    if(p[i].a == p[i].b && p[i].a == 1){
      if(a < k && b < k){
        a++, b++;
        ans += p[i].t;
      }else if(a < k){
        a++;
        ans -= bookb.top();
        bookb.pop();
        ans += p[i].t;
      }else if(b < k){
        b++;
        ans -= booka.top();
        booka.pop();
        ans += p[i].t;
      }else if(!booka.empty() && !bookb.empty() && a >= k && b >= k && booka.top() + bookb.top() > p[i].t){
        ans -= booka.top() + bookb.top() - p[i].t;
        booka.pop(), bookb.pop();
      }
    }
  }
  cout << (a >= k && b >= k ? ans : -1); // 还是凑不出就是无解
  return 0;
}