第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南)C Stone Game【题解】
牛客竞赛传送门:
本题链接:https://ac.nowcoder.com/acm/problem/216161?&headNav=acm
比赛完整题单:https://ac.nowcoder.com/acm/contest/10662
通过率:531/931
题目大意:
有n堆石头,每堆石头由1~3个石头组成,现在要把这n堆石头合并成1堆,每次操作只能两两合并,且会产生费用,求最小费用。费用计算方法:这两堆各含石头x个和y个,合并的费用为(x mod 3) * (y mod 3)。题目第一行给出三个数,第i个数表示由i个石头所组成的堆的堆数是多少。
知识点:贪心、思维题
思路:
因为合并只能两两合并,我们先看看两两合并会发生什么(本文 ~ 表示合并的意思)
1~1 费用为1 | |||
1~2 费用为2 | 2~2 费用为4 | ||
1~3 费用为0 | 2~3 费用为0 | 3~3费用为0 | (4等价为1,不需要继续枚举了) |
1~4(等价于1~1) |
整理上面表格得:
1~1 | 费用为1 | 生成一个新堆,大小为2 | 新堆等价大小为2 |
1~2 | 费用为2 | 生成一个新堆,大小为3 | 新堆等价大小为3 |
2~2 | 费用为4 | 生成一个新堆,大小为4 | 新堆等价大小为1 |
3~x | 费用为0 | 生成一个新堆,大小为3+x | 新堆等价大小为x |
因为我们要计算最后全部合并完的费用,如果剩下的堆的大小都等价为3,那么他们继续合并,就不会增加额外的费用,也就得到了最终答案。所以我们要以生成新堆的大小为3为短期目标,列表观察最小费用的合并方式。
1~1等价大小为2,要再于1合并 | (1~1)~1 | 费用为1+2=3 | 生成一个新堆,大小为3 |
1~2等价大小为3,无需继续合并 | 1~2 | 费用为2 | 生成一个新堆,大小为3 |
2~2等价大小为1,要再与2合并 | (2~2)~2 | 费用为4+2=6 | 生成一个新堆,大小为3 |
3~x等价大小为x | 3~x | 费用为0 | 生成一个新堆,大小为x |
于是发现,我们以多次合并生成等价大小为3的堆作为循环节,费用最小的合并方式是1~2。
由此得到贪心策略:
1、先把所有的1与2合并了先;
2、之后就只剩下两种情况,
①d堆个数为1的堆和个数为3的堆。
②d堆个数为2的堆和个数为3的堆。
那么就只能用(1~1)~1和(2~2)~2这两种策略分别处理;
3、处理后会分别得到三种情况(以剩下的堆是个数为1的 举例):
①d%3==0(即d==0),皆大欢喜,1与2合并后没有剩余。
②d%3==1,也很欢喜,此时情况为:1个个数为1的堆,和很多个个数为3的堆
用3~x的策略,也不会产生新的费用。
③d%3==2,此时情况为:2个个数为1的堆,和很多个个数为3的堆
这两个1合并会产生新的费用,要额外加上。
4、最后再用3~x的策略合并成1堆。这一步不会产生任何费用。这里的x可能为1,2,3。
样例图解:
AC代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a, b, c; cin >> a >> b >> c;
int ans = 0;
if (a == b){
ans = a * 2;
}
else if (a > b){
int d = a - b;//剩下d堆个数为1的堆和个数为3的堆
if (d % 3 == 2)//1 1 3的情况
ans++;
ans += b * 2 + (d - d % 3);
}
else{ // a<b
int d = b - a;//剩下d堆个数为2的堆和个数为3的堆
if (d % 3 == 2)//2 2 3的情况
ans += 4;
ans += a * 2 + (d - d % 3) * 2;
}
cout << ans << "\n";
return 0;
}