acwing 5283. 牛棚入住

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×105，1≤a,b≤2×105，1≤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)$ 小牛栏共有$a$个，每个最多有$1$头牛，小牛栏最多放$a$头牛;
小牛栏有$2$种状态：0头牛和1头牛，用一个变量$a1$表示小牛栏空闲的数量;
$(2)$ 大牛栏共有$b$个，每个最多有$2$头牛，大牛栏最多放$2\ast b$头牛；
大牛栏有$3$种状态：0头牛、1头牛、2头牛，用变量b1表示大牛栏中空闲$1$个栏位的数量，$b2$表示空闲$2$个栏位的数量;
$(3)$ 对于每一波来的牛，可能是$1$头，也可能是$2$头；
用变量$cnt$记录劝离的牛数量;
用变量$f$记录当前在等待入栏的牛的数量;
$(4)$ 来1头牛时：
判断$a1$，若$a1$不为0则表示小牛栏还有空位，不劝离，设置$f=0$;
判断$b2$，若$b2$不为0且$f==1$则表示大牛栏有空位且该牛还在等待，不劝离，设置$f=0$， $b2$自减1，$b1$自增1;
判断$b1$，若$b1$不为0且$f==1$则表示大牛栏有一个空位且该牛还在等待，不劝离，设置$f=0$，$b1$自减1；
$(5)$ 来2头牛时：
判断$b2$，若$b2$不为0则表示大牛栏有空位，不劝离，设置$f=0$，$b2$自减1;
$(6)$ $f$不为0说明此时本波到来的牛被劝离，$cnt$加上$f$就是止至到本波被劝离的牛的数量;

2. 时间复杂度

$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;
}