题解：P11323 【MX-S7-T1】「SMOI-R2」Happy Card

0tAp · 2024-11-24 21:00:36 · 题解

题目链接：P11323 【MX-S7-T1】「SMOI-R2」Happy Card

思路：贪心，这里有两个比较相似的操作，即炸和三带一，对于炸操作可以看成同类牌的一种三带一，因此我们只需要尽可能地完成三带一操作即可，不难发现对于任意大于等于 0 的实数来说，都可以写成 3k，3k+1 和 3k+2 （k 为自然数）的数，因此考虑一个数能分成几个 3 和记录余数 2 和 1 的个数。（不难发现一个 1 对应一个 3，一个 2 对应两个 3）

在下述表达中记 cnt_3,cnt_2,cnt_1 分别为 3，2，1 的个数。

情况一：cnt_3\le cnt_1+2*cnt_2，对于这种情况来说，cnt_3 完全可以和 cnt_1 配对当且仅当 cnt_3\le cnt_1，此时可以直接拿 3 配 1，再直接出单牌和对牌，反之则考虑剩下的 cnt_3 和 cnt_2 能配对几次。

情况二：cnt_3> cnt_1+2*cnt_2，这种情况比较简单，直接给 cnt_1 和 cnt_2 配完，再考虑剩下的 cnt_3 需要几次才能出完即可。

代码如下：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
#define lb(a,b,n) (lower_bound((a)+1,(a)+1+(n),(b))-(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define inf 0x3f3f3f3f
#define llinf 1e18
#define debug cout<<"wwwwwww"
#define xx return
const int N=3e5+10;

int T;
int n;
int v[N];

namespace xx_Tx{
    void solve(){
        int cnt1=0,cnt2=0,cnt3=0;
        rep(i,1,n){
            cnt3+=v[i]/3;
            if(v[i]%3==1)cnt1++;
            if(v[i]%3==2)cnt2++;
        }
        int ans=0;
        if(cnt3<=2*cnt2+cnt1){
            if(cnt3<=cnt1)cout<<ans+cnt1+cnt2<<endl;
            else{
                cnt3-=cnt1;
                ans+=cnt2-cnt3/2+cnt3+cnt1;
                cout<<ans<<endl;
            }
        }
        else{
            ans+=(cnt1+2*cnt2);
            cnt3-=(2*cnt2+cnt1);
            ans+=ceil(cnt3*3.0/4.0)+(cnt3%4==1?1:0);
            cout<<ans<<endl;
        }
        xx;
    }
}

namespace Main_xx{
    void Main(){
        cin>>T;
        while(T--){
            cin>>n;
            rep(i,1,n)cin>>v[i];
            xx_Tx::solve();
        }
        xx;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    Main_xx::Main();
    xx 0;
}