CF762B USB vs. PS/2题解

传送门

本题用贪心，注意开 long long。

思路

题目给了我们 $3$ 类电脑：用 USB 的，用 PS/2 的，和两种都可用的，现在我们要找出尽量多的鼠标满足电脑，并在其基础上尽量花钱少。

对于之能用一种接口的电脑，直接从小到大排序，在要求内尽量多的取最小值。

对于两种接口都能用的电脑，我们直接找剩下的鼠标中最便宜的就行。

实现

只能用一种接口的电脑，直接将对应的接口所有的鼠标从小到大排序，取即可。

两种接口都能用的鼠标，可以将剩下的数拿出来再排序，取够就行；或者直接将数组当队列，记住取到哪了，将两个队头不断更新，取最小即可（代码也是这种思路）。

代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a,b,c;//三种端口 
string t_p;long long x;//临时变量价钱和端口 
long long m;// 鼠标数量 
long long ans,a_s;//花的钱，买的鼠标的数量 
long long a_a[300001],b_b[300001];//存两种鼠标 
long long x_a,x_b;//两种鼠标分别的数量 
int main(){
  cin>>a>>b>>c>>m;
  while(m--){//读入 
    cin>>x>>t_p;
    if(t_p[0]=='P')b_b[x_b++]=x;
    else a_a[x_a++]=x;
  }
  //排序从小到大 
  sort(a_a,a_a+x_a);
  sort(b_b,b_b+x_b);
  for(long long i=0;i<a;i++){//取第一种端口鼠标 
    if(!a_a[i])break;
    ans+=a_a[i],a_s++;
  }
  for(long long i=0;i<b;i++){//取第二种端口鼠标
    if(!b_b[i])break;
    ans+=b_b[i],a_s++;
  }
  for(long long i=0;i<c;i++){//取两种端口鼠标
    if(!a_a[a]&&!b_b[b])break;//鼠标用完了 
    if(a_a[a]<b_b[b]&&a_a[a]&&b_b[b])ans+=a_a[a],a++,a_s++;//两种都还有，取小的队头 
    else if(b_b[b])ans+=b_b[b],b++,a_s++;//只剩第二种了 
    else if(a_a[a])ans+=a_a[a],a++,a_s++;//只剩第一种了 
  }
  cout<<a_s<<" "<<ans<<endl;//输出结果 
  return 0;
}