【CF1374E1】Reading Books (easy version)(贪心)

发布时间 2023-08-30 21:55:47作者: Alric

题目大意:

给出\(n(1\le n\le2\times 10^{5})\)个三元组\((t,a,b)(0\le a,b\le 1)\),选出其中任意个,使得被选中的元素\(a\)\(b\)的总和均为\(k\),求\(t\)总和的最小值


因为被选中的元素\(a\)\(b\)的总和均为\(k\),所以被选中的三元组中,形式为\((t,1,0)\)\((t,0,1)\)的数量相等。

当我们需要加入形式为\((t,1,0)\)\((t,0,1)\)的三元组时,我们可以将这两个三元组配对后同时加入。

配对的方法为分别将形式为\((t,1,0)\)\((t,0,1)\)的三元组按照从小到大排序,将名次相同的三元组\((t_1,1,0)\)\((t_2,0,1)\)配对,将其转化为\((t_1+t_2,1,1)\)

所有的三元组转化为\((t,1,1)\)的形式后,为了使\(t\)总和最小,我们根据\(t\)从小到大进行选择。如果这些三元组的个数不足k个,则这种情况无解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=2e9+10;
ll n,k;
vector<ll> t11,t10,t01;
int main(){
	cin >> n >> k;
	for(ll i=1;i<=n;i++){
		ll t,a,b;
		cin >> t >> a >> b;
		if(a&b)t11.push_back(t);
		else if(a)t10.push_back(t);
		else if(b)t01.push_back(t);
	}
	sort(t10.begin(),t10.end());
	sort(t01.begin(),t01.end());
	for(ll i=0;i<min(t10.size(),t01.size());i++){
		t11.push_back(t10[i]+t01[i]);
	}
	sort(t11.begin(),t11.end());
	if(t11.size()<k){
		cout << -1;
	}else{
		ll ans=0;
		for(ll i=0;i<k;i++){
			ans+=t11[i];
		}
		cout << ans;
	}
	return 0;
}