锐客网

  1. 首页 > it技术 > >

2020.2.22GDUT寒假训练排位赛2-H

H — I Would Walk 500 Miles 题目大意： 【2020.2.22GDUT寒假训练排位赛2-H】农民John想把他的N头奶牛(N≤7500)，方便地编号为1…N，分成K个非空的组(2≤K≤N)，这样两个不同组的奶牛在不走几英里的情况下就不能互相交流。奶牛x和奶牛y(其中1≤x 输入
输入只有一行，包含N和K，用空格隔开。
输出
输出最优解的M。
2020.2.22GDUT寒假训练排位赛2-H
文章图片

题目分析： 每两头牛相见的代价中的最小值，要求的就是这个最小值的最大值。
首先分析一下题目中的式子： (2019201913x+2019201949y) mod 2019201997
也就是：((2019201997-84)x+(2019201997-48)y) mod 2019201997
即： ((-84x-48y) mod 2019201997+2019201997) mod 2019201997
由于x,y都相当较小，所有-84x-48y的结果不会小于-2019201997
所以式子等于：2019201997-84x-48y
在所有牛相见中，代价最小的，肯定是牛N与其他某组的牛组成x和y。x,y越大，式子值越小，最小代价又一定有牛N，所以另外的一头牛要尽可能的小。当1…K-1这几头牛分别各自一组，K…N为一组时，最小代价就是（N，K-1），这样的分组也是所有分组中最小代价最大的那种。
代码实现：

#include #include using namespace std; int main() { int n, k; scanf("%d%d", &n, &k); int ans = 2019201997-84*(k-1)-48*n; printf("%d\n", ans); return 0; }

    推荐阅读


    上一篇：Adroidstudio——listview的使用和arrayadapter的异步更新

    下一篇：2020.2.19GDUT寒假训练排位赛1-I