race 题解

yzy1 · 2021-08-02 07:57:44 · 题解

由于题目中规定 b\le c\le a，我们可以得出一个性质：最大得分策略 A 输的场数不大于 1。对于这个性质，这里有一个简单的证明：

若 A 输的场数为 k(k>1)​​，这几局中 A 与 B 的比分分别为 (a_1,b_1),(a_2,b_2),\cdots,(a_k,b_k)。我们可以将这些同为输的场次合并为一场，即 (a_1+a_2+\cdots+a_k,b_1+b_2+\cdots+b_k)。而剩下的 k-1 场为零比零平局。由于题目保证 b\le c，所以合并后的得分一定不劣于原得分。

同理，我们可以推出第二个性质：最小得分策略 A 赢的场数不大于 1，证明和上一个性质类似，这里不过多讲述。

我们可以采用贪心思想来解决这个问题。

• 对于最大得分，枚举「输 0 场」和「输 1 场」，剩下的场尽可能的赢，实在不行就平局。结果取两种方案最大值。
• 对于最小得分，枚举「赢 0 场」和「赢 1 场」，剩下的场尽可能的输，实在不行就平局。结果取两种方案最小值。

ll mx = -1, mn = 1e18;
if (d >= e) up(mx, min(n, d - e) * a + (n - min(n, d - e)) * c);
up(mx, min(n - 1, d) * a + (e ? b : c) + (n - 1 - min(n - 1, d)) * c);
if (e >= d) down(mn, min(n, e - d) * b + (n - min(n, e - d)) * c);
down(mn, min(n - 1, e) * b + (d ? a : c) + (n - 1 - min(n - 1, e)) * c);