题解：P13171 [GCJ 2017 #2] Fresh Chocolate

· · 题解

看题！

这是一道贪心题，题目要求最大化获得新巧克力的参观团数量。一个团队能获得新巧克力，当且仅当在他们之前，累计消耗的巧克力是每包数量 P 的整数倍，相当于在服务他们之前，巧克力的余数为 0。

怎么做？

为了尽可能多地让余数为 0，可以这样做：

对于人数恰好是 P 的倍数的团队，他们都能吃到新巧克力，且余数为 0，还能让后面的任意人数的团队吃到新巧克力。

对于其他团队，我们要凑出余数为 0 的情况。先凑出两个团队的组合，再凑出三个团队的组合，以此类推，优先用更少的团队凑出 P 的倍数。

这样贪心之后，我们能组合出若干个组合，每个组合都能为答案贡献 1。在所有组合都处理完毕后，如果还有剩下的团队，那么他们中的第一个团队也能获得新巧克力，答案再加 1。

上代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll t,n,p,g,ans,cnt[105];

void solve(ll t){
    cin>>n>>p;
    cl(cnt);
    foru(i,0,n-1){
        cin>>g;
        cnt[g%p]++;
    }
    ans=0;
    if(p==2){
        ans=cnt[0]+cnt[1]/2;
        if(cnt[1]%2)ans++;
    }else if(p==3){
        ans=cnt[0];
        ll min12=min(cnt[1],cnt[2]);
        ans+=min12;
        cnt[1]-=min12,cnt[2]-=min12;
        ans+=cnt[1]/3;
        if(cnt[1]%3!=0)ans++;
        ans+=cnt[2]/3;
        if(cnt[2]%3!=0)ans++;
    }else if(p==4){
        ans=cnt[0];
        ll min13=min(cnt[1],cnt[3]);
        ans+=min13;
        cnt[1]-=min13,cnt[3]-=min13;
        ll min22=cnt[2]/2;
        ans+=min22,cnt[2]%=2;
        ll min12=min(cnt[1]/2,cnt[2]);
        ans+=min12;
        cnt[1]-=min12*2,cnt[2]-=min12;
        ll min32=min(cnt[3]/2,cnt[2]);
        ans+=min32;
        cnt[3]-=min32*2,cnt[2]-=min32;
        ans+=cnt[1]/4;
        cnt[1]%=4;
        ans+=cnt[3]/4;
        cnt[3]%=4;
        if(cnt[1]+cnt[2]+cnt[3]>0)ans++;
    }
    cout<<"Case #"<<t<<": "<<ans<<'\n';
}

int main(){
    cin>>t;
    foru(i,1,t){
        solve(i);
    }
    return 0;
}