题解 P5425 【[USACO19OPEN]I Would Walk 500 Miles】
ix35
2019-06-12 22:11:28
一道很搞笑的结论题。
唯一一篇题解中有提到图论的部分，但是我刚看到这玩意真不觉得是个图论。首先先拆式子吧。
设$P=2019201997$，则$x<y$产生的代价为$((P-84)x+(P-48)y)\mod P$，这个大数看着有点心烦，想办法把它拆去：
$((P-84)x+(P-48)y)\mod P=((-84x-48y)\mod P+P)\mod P$
我们发现由于$N\leq 7500$，因此$-84x-48y$远远不到$-P$，所以内层的取模时可以去掉的，另外由于它总是个负数，因此加上P后不必再取模，外层的取模实际上也是可以去掉的，所以代价为：
$$-84x-48y+P$$
下面让它的最小值取最大值。有一个很显然的结论，最小值一定由$N$和另一个数产生，假设不是这样，那么设最小值由$r<s$组成，那么其中必有一个数与$N$不在一组（否则$r,s$一组矛盾），于是将其中一个换成$N$得到结果更小。
那么当$N$确定时，这个式子的值尽量大，其实就是$x$尽量小，由于$K$组都非空，所以我们让$1...K-1$各自单独一组，最后$K...N$一组，那么$(K-1,N)$可以组成最大的最小值，即：
$$-84(K-1)-48N+P$$
于是就...
注意这玩意看上去大，实际上超小，不会超int，所以随便过。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,k;
int main () {
scanf("%d%d",&n,&k);
printf("%d\n",-12*(7*(k-1)+4*n)+2019201997);
return 0;
}
```