传送门

题意：给定n本书，两个孩子A和B都至少需要读k本书，然后给定n本书的时间和两个孩子对这本书是否喜欢，问两个孩子都读了至少k本书的前提下最少的时间花费是多少？（如果这本书被选择，不论几个人读都是花费t的时间，不喜欢则说明不读）

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：一开始想着像dp，但看了样例二发现是个简单的贪心，我们可以把书分成三类：AB喜欢，A喜欢，B喜欢，我们不妨把A喜欢和B喜欢贪心组合（即A+B的时间最少的组合）变成AB喜欢，我们最后只在AB喜欢中选，其他剩余的没意义，最后AB喜欢排个序，取前k小的AB喜欢即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <string>
 6 #include <vector>
 7 #include <cmath>
 8  
 9 using namespace std;
10  
11 #define ll long long
12 #define pb push_back
13 #define fi first
14 #define se second
15 
16 const int N = 2e5 + 10;
17 
18 void solve()
19 {      
20     int n, k;
21     cin >> n >> k;
22     vector<int > a, b, ab;
23     for(int i = 0; i < n; ++i){
24         int t, x, y;
25         cin >> t >> x >> y;
26         if(x + y == 0) continue;
27         if(x + y == 2) ab.pb(t);
28         else if(x == 1) a.pb(t);
29         else if(y == 1) b.pb(t);
30     }
31 
32     sort(a.begin(), a.end());
33     sort(b.begin(), b.end());
34     int al = a.size();
35     int bl = b.size();
36     int ai, bi;
37     ai = bi = 0;
38     while(ai < al && bi < bl){
39         ab.pb(a[ai++] + b[bi++]);
40     }
41     sort(ab.begin(), ab.end());
42     int abl = ab.size();
43 
44     if(abl < k) cout << "-1" << endl;
45     else{
46         int Min = 0;
47         for(int i = 0; i < k; ++i){
48             Min += ab[i];
49             //cout << "ab[i] = " << ab[i] << endl;
50         }
51         cout << Min << endl;
52     }
53 }
54  
55 int main()
56 {
57     ios::sync_with_stdio(false);
58     cin.tie(0);
59     cout.tie(0); 
60     solve();
61  
62     return 0;
63 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄