CF1374E1 Reading Books (easy version)

Reading Books (easy version)

题目大意：Alice和Bob一共有$n$本书要读。第$i$本书有三个属性：阅读时间$t_i$,$a_i$(为$1$表示 Alice喜欢这本书,为$0$表示Alice不喜欢),$b_i$(为$1$表示Bob喜欢这本书,为$0$表示Bob不喜欢)
他们需要从这些书中选择若干本，满足：

• 这些书中至少有$k$本是Alice喜欢的，至少有$k$本是Bob喜欢的。
• 阅读的总时间最小（总时间为选中的书的$t_i$的总和）

思路：思维题
对于这$n$本书，我们可以分为三类，A、B都喜欢的，A喜欢的，B喜欢的(都不喜欢的书直接扔了)我们把这三类书每本所花时间用三个数组$t_1$、$t_2$、$t_3$记录

• 因为A、B都要至少有$k$本喜欢，那么我们判断到底能否满足这个条件就看$t_1.size+min(t_2.size,t_3.size)>=k$是否成立
• 为了让时间尽量小，首先我们将$t_2$、$t_3$按升序排序，取$min(t_2.size,t_3.size)$个，将对应和加入$t_1$，再将$t_1$升序排序，取前$k$项即为所求

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
typedef long long ll;

ll n,k,t1[N],t2[N],t3[N];
ll a,b,c;
int main(){
	ll cnt1=0,cnt2=0,cnt3=0;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		if(b==0&&c==0) continue;
		if(b==1&&c==0) t1[++cnt1]=a;
		if(b==0&&c==1) t2[++cnt2]=a;
		if(b==1&&c==1) t3[++cnt3]=a;
	}	
	sort(t1+1,t1+cnt1+1);
	sort(t2+1,t2+1+cnt2);
	for(int i=1;i<=min(cnt2,cnt1);i++) t3[++cnt3]=t1[i]+t2[i];
	sort(t3+1,t3+1+cnt3);
	ll ans=0;
	if(cnt3<k) cout<<"-1"<<endl;
	else{
		for(int i=1;i<=k;i++) ans+=t3[i];
		cout<<ans<<endl;
	}
	return 0;
}