首页 > 代码库 > CodeForce-762B USB vs. PS/2(贪心)
CodeForce-762B USB vs. PS/2(贪心)
USB vs. PS/2
CodeForces - 762B
题意:有三种电脑,分别有a、b、c个,第一种只有USB接口,第二种只有PS/2接口,第三种有两种接口,有m个鼠标,告诉你价钱和接口类型,问最多有多少电脑和鼠标可以配对,这些鼠标最少花多少钱。
Input
2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2
Output
3 14
解题思路:将两种鼠标分类后根据价钱来排序,先处理只有USB和只有PS/2接口的,然后两种鼠标取价钱少的来处理既有USB又有PS/2接口的
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> using namespace std; #define LL long long int a,b,c; int m; LL x1[300009],x2[300009]; int main() { while(~scanf("%d %d %d",&a,&b,&c)) {//读取数据过多,cin超时 int sum1=0,sum2=0; memset(x1,0,sizeof x1); memset(x2,0,sizeof x2); LL q,ans=0; string p; scanf("%d",&m); while(m--) { cin>>q>>p; if(p=="USB") x1[sum1++]=q; else x2[sum2++]=q; } sort(x1,x1+sum1); sort(x2,x2+sum2); int aa=min(a,sum1),bb=min(b,sum2),sum=aa+bb,k=0; while(k<c) { if(aa<sum1&&bb<sum2&&x1[aa]<x2[bb]) aa++; else if(aa<sum1&&bb<sum2) bb++; else if(aa<sum1) aa++; else if(bb<sum2) bb++; else break; sum++; k++; } for(int i=0;i<aa;i++) ans+=x1[i]; for(int i=0;i<bb;i++) ans+=x2[i]; printf("%d %lld\n",sum,ans); } return 0; }
CodeForce-762B USB vs. PS/2(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。