网站策划案范文,百度添加到桌面,佛山 做网站公司有哪些,专做服装的网站题目 - 点击直达 1. 5283. 牛棚入住1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 5283. 牛棚入住
1. 题目详情
贝茜经营的牛棚旅店中有 a 个可供一头牛入住的小牛栏和 b 个可供两头牛入住的大牛栏。
初始时#xff0c… 题目 - 点击直达 1. 5283. 牛棚入住1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 5283. 牛棚入住
1. 题目详情
贝茜经营的牛棚旅店中有 a 个可供一头牛入住的小牛栏和 b 个可供两头牛入住的大牛栏。
初始时所有牛栏都是空的。
已知今天一共有 n 波奶牛依次前来入住每波由 1∼2 头奶牛组成。 如果是一头奶牛前来入住那么 如果有空着的小牛栏则安排其在空着的小牛栏入住。如果没有空着的小牛栏则安排其在空着的大牛栏入住。如果既没有空着的小牛栏也没有空着的大牛栏则安排其在仍未住满的大牛栏入住。如果上述都没有则将其劝离。 如果是两头奶牛前来入住那么 如果有空着的大牛栏则安排它们在空着的大牛栏入住。如果没有空着的大牛栏则将它们劝离。请你计算一共有多少头奶牛会被劝离。 注意问题是被劝离的奶牛具体数量而不是波数。
1. 原题链接
acwing 5283. 牛棚入住
2. 题目要求
输入格式 第一行包含三个整数 n,a,b。
第二行包含 n 个整数 t1,t2,…,tn其中 ti 表示第 i 波奶牛的数量。
输出格式 一个整数表示被劝离的奶牛的具体数量。
数据范围 前 3 个测试点满足 1≤n≤5。 所有测试点满足 1≤n≤2×1051≤a,b≤2×1051≤ti≤2。 输入样例1 4 1 2 1 2 1 1 输出样例1 0 输入样例2 4 1 1 1 1 2 1 输出样例2 2 3. 基础框架
● Cpp代码框架
#include iostream
using namespace std;
int main(){return 0;
}2. 解题思路
1. 思路分析 ( 1 ) (1) (1) 小牛栏共有 a a a个每个最多有 1 1 1头牛小牛栏最多放 a a a头牛; 小牛栏有 2 2 2种状态0头牛和1头牛用一个变量 a 1 a1 a1表示小牛栏空闲的数量; ( 2 ) (2) (2) 大牛栏共有 b b b个每个最多有 2 2 2头牛大牛栏最多放 2 ∗ b 2*b 2∗b头牛 大牛栏有 3 3 3种状态0头牛、1头牛、2头牛用变量b1表示大牛栏中空闲 1 1 1个栏位的数量 b 2 b2 b2表示空闲 2 2 2个栏位的数量; ( 3 ) (3) (3) 对于每一波来的牛可能是 1 1 1头也可能是 2 2 2头 用变量 c n t cnt cnt记录劝离的牛数量; 用变量 f f f记录当前在等待入栏的牛的数量; ( 4 ) (4) (4) 来1头牛时 判断 a 1 a1 a1若 a 1 a1 a1不为0则表示小牛栏还有空位不劝离设置 f 0 f0 f0; 判断 b 2 b2 b2若 b 2 b2 b2不为0且 f 1 f1 f1则表示大牛栏有空位且该牛还在等待不劝离设置 f 0 f0 f0 b 2 b2 b2自减1 b 1 b1 b1自增1; 判断 b 1 b1 b1若 b 1 b1 b1不为0且 f 1 f1 f1则表示大牛栏有一个空位且该牛还在等待不劝离设置 f 0 f0 f0 b 1 b1 b1自减1 ( 5 ) (5) (5) 来2头牛时 判断 b 2 b2 b2若 b 2 b2 b2不为0则表示大牛栏有空位不劝离设置 f 0 f0 f0 b 2 b2 b2自减1; ( 6 ) (6) (6) f f f不为0说明此时本波到来的牛被劝离 c n t cnt cnt加上 f f f就是止至到本波被劝离的牛的数量;
2. 时间复杂度 O ( N ) O(N) O(N) 每波需要对到来的牛判断共有n波每波内的判断是常数次;
3. 代码实现
#include iostream
using namespace std;int main(){// 输入处理int n,a,b;cin n a b;int arr[n];for(int i 0; i n; i){int tmp;cin tmp;arr[i] tmp;}// 逻辑处理int a1 a;int b1 0;int b2 b;int cnt 0;for(int i 0; i n; i){if(arr[i] 1){if(a1 ! 0){a1--;arr[i] 0;}if(b2 ! 0 arr[i] 1){b2--;b1;arr[i] 0;}if(b1 ! 0 arr[i] 1){b1--;arr[i] 0;}}else{if(b2 ! 0){b2--;arr[i] 0;}}cnt arr[i];}// 输出cout cnt endl;return 0;
}
