题解：P5425 [USACO19OPEN] I Would Walk 500 Miles G

· · 题解

P5425 I Would Walk 500 Miles G 题解

分析

题目要求将 N 头奶牛分为 K 组，使得不同组间的最小距离 M 最大化。距离公式为：d(x,y) = (2019201913x + 2019201949y) \bmod 2019201997

如果你学过模运算的概念，那么你就可以化简为下面这个式子：

d(x,y) = 2019201997 - (84x + 48y)

其中 84x + 48y < 2019201997。要使 M 最大化，需最小化跨组边中 84x + 48y 的最大值。

将最大的 N-K+1 头奶牛分为一组，其余 K-1 头各单独成组。此时跨组边的最大值为：84(K-1) + 48N

此分组策略确保跨组边中 84x + 48y 的最大值最小。对应的 M 为：M = 2019201997 - ( 48N + 84(K-1) )

验证一下，当 N=3,K=2 时：

48 \cdot 3 + 84 \cdot (2-1) = 228 \implies M = 2019201997 - 228 = 2019201769

可以看出符合样例，所以这个公式应该是正确的。

综上所述，M 的值为 2019201997 - (48N + 84(K-1))。

代码

直接带入就可以了。