题解归档 - cf2230A

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

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

思路

cf2230A

pattern: group-size local optimization.

claim: It is enough to use full groups of three when the group key is beneficial, and handle the remainder by min(remainder singles, one group key). Compare this with buying all singles.

necessary: Any group key covers at most three students, so full triples are the only place where grouping can beat three individual keys.

sufficient: Cover floor(n/3) triples by group keys, then cover the last 0/1/2 students either individually or with one group key. Taking min with n*a handles the case where group keys are never useful.

brute/check: For small n enumerate the number of bought group keys from 0 to ceil(n/3), cover the rest by singles, and compare with the formula.

edge: n=1 can still use one group key; costs need 64-bit.

代码

来源：problems/cf2230A/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll t,n,a,b,zc,cnt,ans;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&a,&b);
        ans=n/3*b;
        zc=n%3;
        cnt=zc*a;
        if(b<cnt) cnt=b;
        ans+=cnt;
        if(n*a<ans) ans=n*a;
        printf("%lld\n",ans);
    }
    return 0;
}