第 45 届ICPC亚洲区域赛（济南）C Stone Game【题解】

牛客竞赛传送门：

本题链接：Stone Game

题目大意

有$3$个数据a₁、a₂、a₃，其中a_i表示数量为i的石头的堆数，假如a₁=$99$，那么数量为$1$的石头有$99$堆。现在要把那么多堆石头合并成$1$堆，每次只能两两合并且会付出代价，求最小代价。代价的计算方法：假如这两堆的数量分别是x和y，那么合并的费用为$$(xmod3)\ast (ymod3)$$

样例

输入
99 66 55
输出
165

算法及思路

贪心。
思路：观察可得，合并一入1和不2消耗体力为2。合并1消耗体力为1的个数乘1，合并2消耗体方为2的个数乘2。3是不用管的。最优方案肯定是合并完1和2再合并剩余的1或2。那么分类讨论就行了

证明思路

引理：由于$3$mod$3$＝$0$，那么需要尽量凑出足够多的$3$，在$1$和$2$的数量都大于$0$的时候，先合并$1$和$2$可以凑出更多$3$，此时是a₁ a₂ 0（a₁ > a₂）。 即证明：在$1$和$2$的数量都大于$0$时，先合并$1$和$2$可以在更小的体力下产出更多的$3$。
反证：若不先合并$1$和$2$，即合并$1$和$1$或$2$和$2$，不失一般性，下面讨论$1$和$1$。由于先合并$1$和$1$会产生体力消耗为$a1/2$，堆变为$0$、 $(a2+a1)/2$、 $0$，此时便只能合并$2$和$2$，不难看出，合并完$2$后体力消耗$2\ast a2+a1$，此时共消耗的体力已经达到$2\ast a2+1.5\ast a1$。由下面推导可得按最优解合并完后消耗的体力为$a1+a2$，显然更优。

下面的$1$ $2$ $3$表示数量为几个(包括$3$的整数倍➕余数，即$4$ $7$算进$1$，$5$ $8$算进$2$，$6$ $9$算进3，以此类推)，设堆数为a₁ a₂ a₃
①若先合并$1$和$3$或$2$和$3$都只会消耗$3$(因为($1$+$3$)mod$3$=$1$,即$1$和$2$的堆数并不改变)，下面讨论合并$1$和$3$。($2$和$3$同理)
消耗完$3$后，体力消耗$0$，堆数为a₁ a₂ 0，此时只能合并$1$和$2$，不失一般性，设a₁＞a₂，那么一对一合并完后，堆数为a₁ - a₂，体力消耗$2$ * a₂，此时的决策是当前最优。引理：由于$3$mod$3$＝$0$，那么需要尽量凑出足够多的$3$，在$1$和$2$的数量都大于$0$的时候，先合并$1$和$2$可以凑出更多$3$。合并后的样子是a₁ - a₂ 0 0，这里有多种合并方式，我取两种极端的例子，其余例子所消耗的体力必然在这两者消耗体力所构成的闭区间内，下面会给出该证明。
(1)单方面整块合并$1$或$2$($x$ ＝ a₁ - a₂)，合并后消耗体力为$x/2$，堆数写得繁琐便不再赘述，此时$2$中有$x/2$堆，继续单方面合并，消耗$x/4\ast 2$体力，以此类推，最后所得消耗体力是$$x+x/4+...+x/(4^{n-1})$$ 此时x大于等于4的n-1次方，自行解n。
(2)利用$2$ $0$ $0$消耗体力$2$，$3$ $0$ $0$消耗体力$3$，$0$ $2$ $0$消耗体力$4$，$0$ $3$ $0$消耗体力$6$这种合并配凑的方式进行合并，那么a₁ - a₂ $0$ $0$合并后所消耗的体力值应为a₁ - a₂，即消耗体力$x$。显然第二个更优。

②若先合并$1$和$2$，即a₁ a₂ a₃变为a₁ - a₂ $0$ a₃，消耗体力$2\ast a2$，与以上一致，因此一开始先合并谁都不影响最优解，因为只要3存在，且合并时包含$3$消耗体力都为$0$且只消耗$3$。

不严谨证明：为何“其余例子所消耗的体力必然在这两者消耗体力所构成的闭区间内”？
由于第一种合并方式消耗的体力值要么为$1$要么为$4$，而第二种消耗的体力值为$1$或$2$，在合并相同性质数量的区间的条件下，合并方式便是影响消耗体力的最大因素。若采取其余合并方式有$1$ $2$ $4$的可能性，有$2$的加入，显然比第一种优，有$4$的加入必然比第二种劣

代码

#include 
#include 
#include 
#define reg register
#define int long long
using namespace std;
const int N=1e5+5;
int n,m;
int a,b,c;
signed main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>a>>b>>c;
    int ans=0;
    if(a==b)
    {
        ans=a*2;
    }
    else if(a>b)
    {
        int d=a-b;
        if(d%3==2) ans++;
        ans+=b*2+(d-d%3);
    }
    else
    {
        int d=b-a;
        if(d%3==2) ans+=4;
        ans+=a*2+(d-d%3)*2;
    }
    cout<<ans<<"\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

以上皆为个人观点，如有不严谨的地方请指出。