【C++贪心】P11044 [蓝桥杯 2024 省 Java B] 食堂|普及

本文涉及知识点

C++贪心

[蓝桥杯 2024 省 Java B] 食堂

题目描述

S 学校里一共有 $a_2$ 个两人寝、 $a_3$ 个三人寝， $a_4$ 个四人寝，而食堂里有 $b_4$ 个四人桌和 $b_6$ 个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐，请问这个食堂最多同时满足多少同学用餐？

输入格式

本题采用多组数据输入。

输入共 $q + 1$ 行。

第一行为一个正整数 $q$ 表示数据组数。

后面 $q$ 行，每行五个非负整数 $a_2,a_3,a_4,b_4,b_6$ 表示一组数据。

输出格式

输出共 $q$ 行，每行一个整数表示对应输入数据的答案。

样例 #1

样例输入 #1

2
3 0 1 0 1
0 2 2 1 1

样例输出 #1

6
10

提示

【样例说明】

对于第一组数据，只有一个六人桌，因此最多安排三个两人寝的同学就餐，答案为 $(2 + 2 + 2) = 6$ 。

对于第二组数据，用一个六人桌安排两个三人寝的同学，用一个四人桌安排一个四人寝的同学，答案为 $(3 + 3) + (4) = 10$ 。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $a_2+a_3+a_4\leq 8$ 。

对于 $100\%$ 的评测用例，保证 $q\leq 100$ ， $b_4+b_6\leq a_2+a_3+a_4\leq 100$ 。

贪心（错误）

性质一：a3先住b6，再住b4。假定某方案a3住b4，且某个b6不是2个3。如果此b6后空闲，则移动b6，否则交换之。规则如下：
b6是2+2+2，2+4,2+2或4或3换。
b6是2+3,2和3换。
b6是4或2+2，全部和b4换。
枚举i个a3吃饭。优先住b6，其次住b4。如果有单个a3住a6，可以再加一个a2。
a4住b4，不足够的a4和a2一起住b6。
a2住剩下的b4, b6。
错误：a3不一定住完。

贪心

6人桌

状态63:3+3，含义6人桌坐了a3,a3。
状态62:4+2
状态61:2+2+2
状态50 ：2+3
状态42： 4
状态41： 2+2
状态20:2
状态30:3
证明状态63不劣于任何状态:
非状态63的3有如下情况：4或6只有3,3+2，空闲的3。如果两个空闲的3，合成一个可交换的6的位置，可以替换任意的状态。否则4或6的3提供4的位置，另外一个3提供3的位置，可以替换任何状态。
证明状态62不劣于比它低的状态：
4+2两个空位，可以交换任意比它低的状态。
证明状态61不劣比它低的状态：
比它低的状态2，只有四种情况：2+3,2+2,2,空闲2。2+3只能有一个，否则转换成3+3了。如果有两个空闲的2,则组成空闲的4。从2+2和2，找2个，交换成4的空位。如果找不到，说明有空闲的2。空闲的2和2+2交换，交换成4的空位。于是有4+2的空位。
状态50不劣比它低的状态：
如果3不是空闲状态，可以提供4+2的空位。可以替换任意比它低的状态。如果是空闲，能替换状态42以外的状态。3空闲，不能2独占4人桌或6人桌。故3空闲，2+2占4人桌或6人桌，4占6人桌。劣于4+2,3,2空闲。这种状态是非最优解，无需讨论。
状态42不劣比它低的状态：
4的空位和任何比它低的状态交换。
状态41不劣比它低的状态：
2个要么是空闲状态，要么是独占4人桌或6人桌。独占可以提供4人的位置。2个空闲也可以提供4人的位置。
状态20不劣比它低的状态：
无论3是空闲的还是独占4人桌，都可以换。
结论：任意高状态不劣于低状态。故优先枚举高状态。

4人桌

4人桌的证明过程和6人桌同。

结题思路

状态从高到底枚举6人5人桌。枚举完后，6人桌和4人桌完全相同。b4 += b6。继续枚举如下状态。
不需要每次都增加ans。可以 ans = 2a2+3a3+4a4。操作结束后：ans -=( 2a2+3a3+4a4)。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>#include <bitset>
using namespace std;template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {vector<T> ret;T d ;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}template<class T = int>
vector<T> Read( const char* pFormat = "%d") {int n;scanf("%d", &n);vector<T> ret;T d;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}class Solution {public:int MaxS(int a2,int a3,int a4,int b4,int b6) {int ans = 0;auto Do6 = [&]() {const int i33 = min(a3 / 2, b6);//2个a3住b6					a3 -= i33 * 2;b6 -= i33;ans += 6 * i33;const int i42 = min(min(a4, a2), b6);//a4+a2=6a4 -= i42;a2 -= i42;b6 -= i42;ans += 6 * i42;const int i222 = min(a2 / 3, b6);a2 -= 3 * i222;b6 -= i222;ans += 6 * i222;const int i23 = min(min(a2, a3), b6);a2 -= i23;a3 -= i23;b6 -= i23;ans += 5 * i23;					};auto Do4 = [&]() {int i4 = min(a4, b4);a4 -= i4;b4 -= i4;	ans += 4 * i4;int i22 = min(a2 / 2, b4);a2 -= 2 * i22; b4 -= i22; ans += 4 * i22;const int i3 = min(a3, b4);a3 -= i3; b4 -= i3; ans += 3 * i3;};Do6();b4 += b6; b6 = 0;Do4();const int i2 = min(a2, b4);ans += 2 * i2;return ans;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint T;	scanf("%d", &T);while (T--) {int a2, a3, a4, b4, b6;scanf("%d%d%d%d%d", &a2,&a3,&a4,&b4,&b6);auto res = Solution().MaxS(a2, a3, a4, b4, b6);cout << res << std::endl;}return 0;
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功