傳送門
題意：給定n本書，兩個孩子A和B都至少需要讀k本書，然后給定n本書的時間和兩個孩子對這本書是否喜歡，問兩個孩子都讀了至少k本書的前提下最少的時間花費是多少？（如果這本書被選擇，不論幾個人讀都是花費t的時間，不喜歡則說明不讀）
思路：一開始想著像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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17899.html
標籤：其他
上一篇：CF 1379 A. Acacius and String
下一篇：懸線法-最大子矩形