USACO 2020 Open Gold P2

USACO analysis

---

肖肖 | 17 Nov 2020

报告错误

如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：

1. 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
2. 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库

题目

给出N头牛要求分成K个分组,每个分组至少一头牛,不同分组中的任意两头牛的之间距离为(2019201913x+2019201949y) mod 2019201997,令M为某种情况中的最短距离,问当M尽量大时,M的值

分析

首先题目中的距离式子看着比较复杂所以我们进行以下化简

由化简得到的结果我们可以看出当x和y越大时,距离越短,所以为了使M尽可能地大,可以将大的数字一直往后放在一起,然后M就可以等于可以等于20192019-84x-48n,而x应该是把最大的数分完到一组后剩下的数的最大的数,就是前面K-1个组合都放一头奶牛然后最后放剩下的所有的牛,最后得到的其实M就等于20192019-84(K-1)+48*N

复杂度

O(1)由分析中可以推导出可以直接得到关于M的式子的答案,代入计算就行

代码

#include <stdio.h>
#include <stdlib.h>

using namespace std;

int N,K;

int main(){
	FILE *in = fopen("walk.in","r");
	FILE *out = fopen("walk.out","w");
	fscanf(in,"%d%d",&N,&K);
	fprintf(out,"%d",2019201997-84*(N-(N-K+1))-48*N);
	return 0;
}

评论区