题意:
有n堆石头,每堆石头最多只有三个石头(最少1个),每两堆石头(这两堆各含石头x个和y个)合一起的费用为(x mod 3) * (y mod 3),现在把所有堆合成一堆,问最小费用
题目第一行给出三个数,第i个数表示有i个石头的堆有多少个
题解:
费用是(x mod 3) * (y mod 3),那也就是说如果x和y有一个是3的倍数,那么费用就是0,那么我们就要将堆内石头尽可能构造3的倍数
比如:一个石头和两个石头合并,费用是2
三个堆,每个堆都只有一个石头,费用是1+2 = 3
三个堆,每个堆都只有两个石头,费用是4+2 = 6
说明一个石头和两个石头构造更划算
那么我们一开始就让1个石头的堆和两个石头的合并,然后多余的自己合并
详细看代码
代码:
#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48); return s*w; } int main() { ll x,y,z; cin>>x>>y>>z; ll ans=0; ans=min(x,y)*2; if(x>y) { x-=y;//还剩下x堆只有一个石头的石头堆 ans+=x/3*3;//和成三个石头的堆 if(x%3==1)ans+=0; if(x%3==2)ans+=1; } else if(y>x) { y-=x; ans+=y/3*6; if(y%3==2)ans+=4; } cout<<ans; }