专栏文章

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

00tAp
P11323题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir0ah1h
此快照首次捕获于
2025/12/04 13:39
3 个月前
此快照最后确认于
2025/12/04 13:39
3 个月前
查看原文
题目链接：P11323 【MX-S7-T1】「SMOI-R2」Happy Card
思路：贪心，这里有两个比较相似的操作，即炸和三带一，对于炸操作可以看成同类牌的一种三带一，因此我们只需要尽可能地完成三带一操作即可，不难发现对于任意大于等于 00 的实数来说，都可以写成 3k3k，3k+13k+1 和 3k+23k+2 （kk 为自然数）的数，因此考虑一个数能分成几个 33 和记录余数 22 和 11 的个数。（不难发现一个 11 对应一个 33，一个 22 对应两个 33）
在下述表达中记 cnt3,cnt2,cnt1cnt_3,cnt_2,cnt_1 分别为 3，2，13，2，1 的个数。
情况一：cnt3≤cnt1+2∗cnt2cnt_3\le cnt_1+2*cnt_2，对于这种情况来说，cnt3cnt_3 完全可以和 cnt1cnt_1 配对当且仅当 cnt3≤cnt1cnt_3\le cnt_1，此时可以直接拿 33 配 11，再直接出单牌和对牌，反之则考虑剩下的 cnt3cnt_3 和 cnt2cnt_2 能配对几次。
情况二：cnt3>cnt1+2∗cnt2cnt_3> cnt_1+2*cnt_2，这种情况比较简单，直接给 cnt1cnt_1 和 cnt2cnt_2 配完，再考虑剩下的 cnt3cnt_3 需要几次才能出完即可。
代码如下：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...