题解：P12249 [科大国创杯初中组 2025] 果汁

Wide_Master · 2025-04-20 14:33:58 · 题解

思路

考虑贪心。

我们读题可知，a_i 单调递增，这可以让我们免去一些复杂的代码。

然后，我们换一个想法，我们把 V_i 看作是还能装下多少单位果汁，然后我们分类讨论三种可能：

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+7;
int T,n,m,v[N],a[N],ans;
int main()
{
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=m;i++)
            cin>>v[i];
        for(int i=1;i<=n;i++)
            cin>>a[i];
        ans=0;//记得多测清空
        for(int i=1;i<=n;i++){
            if(v[a[i]]&&v[a[i]+1])v[a[i]+1]--;
            else if(v[a[i]])v[a[i]]--;
            else if(v[a[i]+1])v[a[i]+1]--;
            else ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}