御坂妹妹非常的可爱,而且会有的时候会很挑食。比如晚餐,有的御坂妹妹只吃素食,还有的只爱吃荤菜,当然也有对此感到无所谓的。
现在已知有a个御坂妹妹只爱吃素菜,有b个御坂妹妹只吃荤菜,还有c个御坂妹妹二者都能接受,上条当麻要为她们买晚饭。
商店共提供m种菜,并且规定每种菜只能买一次。
每一种菜有一个价格ci以及一个种类,表示是荤菜还是素菜。
现在上条当麻想要喂饱尽可能多的御坂妹妹,并且希望尽可能的减少花费。
请你告诉他他最多能喂饱多少个御坂妹妹,以及至少要花费多少钱。
第一行三个整数a、b、c。
接下来一行是一个整数m接下来m行,每行表示食品的价值和类别,A表示素菜,B表示荤菜。
两个数,分别表示能够喂饱的御坂妹妹数量以及花费的总价值。
样例输入 #1
2 1 1
4
5 A
6 B
3 B
7 B
样例输出 #1
3 14
对于10%的数据,保证a=b=0
对于30%的数据,保证 1≤ a,b,c≤100, 1≤m≤100
对于100%的数据,保证1≤a,b,c≤, 1≤m≤3×
所有的 ci≤
这道题是一道排序+贪心,不是特别难,那我们分解来做。
1.排序
这道题在排序时要考虑到既要从小到大排价格,还要做到两种类型同时变,那用什么排序呢?作者第一反应是冒泡,开一个结构体比较价钱,再swap一下,这就是冒泡的思路,但在测试后发现大数据会TLE。
结构体+冒泡不行,那就用时间复杂度最低的排序sort,结构体不行我就用pair至于pair是什么补充里说,然后来到下一步。
2.求价格和喂饱的数量
这个比较简单了,因为有的人会挑食,所以我们先考虑一下挑食的人,最后搞不挑食的,这不用说代码吧?
就问你简单不!!
1.结构体
结构体可以理解为是自定义的类型,里面可以包含平时用的int、long long、char、string...... 首先,怎么定义?
struct 自定义类型的名称{
//定义变量吧
};//记住这个封号别忘了,作者踩过的坑
定义完了,怎么用?
//这里假设自定义类型叫p
p a;//定义个变量
p b[10010]//定义个数组
//当我们要用变量时
a.结构体里的变量;
b[填数字].结构体里的变量;
注:万能头 #include <bits/stdc++.h> 就可以了除非你要装13
会用了, 举个样例代码吧。
样例代码:
会用了不?
2.pair的用法
当我们想要两个元素捆绑在一起作为一个合成元素,又不想要因此定义结构体时,使用pair可以很方便地作为一个代替品。pair实际上是可以看作一个内部有两个元素的结构体,且这两个元素类型是可以指定的,嘿,简单不!
先说下,这个也用万能头!
定义也很简单!
pair<类型1,类型2>变量名;//变量
pair<类型1,类型2>数组名;//数组
使用时和结构体差不多,但有差别。
//假设变量和数组名为a,b
a.first或a.second
b[].first或b[].second
样例代码: