题解归档 - cf2228A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2228A
• 本地来源：problems/cf2228A/idea.md
• 题目链接：https://codeforces.com/contest/2228/problem/A
• 原始标题：cf2228A

思路

cf2228A

pattern: count residues modulo 3.

claim: Every zero can be removed alone. For residues 1 and 2, a pair (1,2) uses two elements for one operation and is always at least as good as waiting for triples. After all pairs are used, only one residue remains, and each operation needs three of it.

answer: cnt0 + min(cnt1,cnt2) + abs(cnt1-cnt2)/3.

edge: all zeroes, only ones, only twos.

代码

来源：problems/cf2228A/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
int main(){
    ll t,n,i,x,c0,c1,c2,ans,dq;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        c0=c1=c2=0;
        for(i=1;i<=n;i++){
            scanf("%lld",&x);
            if(x==0) c0++;
            else if(x==1) c1++;
            else c2++;
        }
        dq=min(c1,c2);
        ans=c0+dq+(max(c1,c2)-dq)/3;
        printf("%lld\n",ans);
    }
    return 0;
}