首页 > 其他分享 >Sleepy Cow Herding

Sleepy Cow Herding

时间:2024-12-13 20:27:13浏览次数:6  
标签:Herding 移动 Cow int 位置 Sleepy John Farmer 奶牛

题目描述

Farmer John 的三头获奖奶牛 Bessie、Elsie 和 Mildred,总是会迷路走到农场上遥远的地方去!他需要你帮助将她们一起赶回来。农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴,奶牛可以占据数轴上的任意整数位置。这 3 头奶牛现在正位于不同的整数位置,Farmer John 想要移动她们,使得她们占据三个相邻的位置(例如,位置 6、7、8)。

不幸的是,奶牛们现在很困,Farmer John 要让她们集中精力听从命令移动并不容易。任意时刻,他只能使得一头处在“端点”(在所有奶牛中位置最小或最大)位置的奶牛移动。当他移动奶牛时,他可以命令她走到任意一个未被占用的整数位置,只要在新的位置上她不再是一个端点。可以看到随着时间的推移,这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

输入格式

输入包含一行,包括三个空格分隔的整数,为 Bessie、Elsie 和 Mildred 的位置。每个位置均为一个范围 1…10^9 内的整数。

输出格式

输出的第一行包含 Farmer John 需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。(注意:移动时至少有一头奶牛位置不会变)

输入样例
4 7 9
输出样例
1
2

样例解释

最小移动次数为 1——如果 Farmer John 将位置 4 的奶牛移动到位置 8,那么奶牛们就处在连续的位置 7、8、9。最大移动次数为 2。例如,位置 9 的奶牛可以被移动到位置 6,然后位置 7 的奶牛可以被移动到位置 5。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	int a[3];
	scanf("%d %d %d", a, a + 1, a + 2);
	sort(a, a + 3);
	int s;
	if (a[2] - a[0] == 2) s = 0;
	else if (a[1] - a[0] == 2 || a[2] - a[1] == 2) s = 1;
	else s = 2;
	int d = max(a[2] - a[1] - 1, a[1] - a[0] - 1);
	printf("%d\n%d", s, d);

	return 0;
}

标签:Herding,移动,Cow,int,位置,Sleepy,John,Farmer,奶牛
From: https://blog.csdn.net/ZycNotFound/article/details/144436403

相关文章

  • USACO备考冲刺必刷题 | P1676 Aggressive cows
    学习C++从娃娃抓起!记录下USACO(美国信息学奥赛)备考学习过程中的题目,记录每一个瞬间。附上汇总贴:USACO备考冲刺必刷题|汇总-CSDN博客【题目描述】农夫约翰建造了一座有 n 间牛舍的小屋,牛舍排在一条直线上,第 i 间牛舍在 xi 的位置,但是约翰的 m 头牛对小屋很不满意,因......
  • 题解:[USACO07DEC] Sightseeing Cows G
    洛谷P2868题目大意有个$n$个点,$m$条边的有向图,点有点权,边有边权。现在要找出一个环,使得点权和与边权和的比值最大。思路既然说要使得点权和与边权和的比值最大,那么就会想到$01$分数规划。二分答案就不用说了,重点是这个$check$函数。$01$分数规划的板子中要检查的是......
  • P2863 [USACO06JAN] The Cow Prom S
    https://www.luogu.com.cn/problem/P2863[USACO06JAN]TheCowPromS题目描述有一个n个点,m条边的有向图,请求出这个图点数大于1的强连通分量个数。输入格式第一行为两个整数n和m。第二行至m+1行,每一行有两个整数a和b,表示有一条从a到b的有向边。输出格式......
  • [USACO03Open] Lost Cows
    题目Description有 NN 头奶牛,已知它们的编号为 1∼N1∼N 且各不相同,但不知道每头奶牛的具体编号。现在这 NN 头奶牛站成一列,已知第 ii 头奶牛前面有 aiai​ 头牛编号小于它,求每头奶牛的编号。Input第 11 行,输入一个整数 NN第 2...N2...N 行,每行输入一个......
  • 题解:P9938 [USACO21OPEN] Acowdemia II B
    首先根据每篇出版物构建一个资历比较矩阵\(g\),其中\(g_{a,b}=1\)表示研究员\(a\)比\(b\)资历更高。遍历每篇出版物,识别出第一个降序的名字,然后假定该名字之后的所有研究员资历都比当前名字对应的研究员资历高即可。代码:#include<bits/stdc++.h>usingnamespacestd;......
  • P3067 [USACO12OPEN] Balanced Cow Subsets G
    我的天,折半搜索(meetinthemiddle),依稀记得我学过,但是真的不记得。。。。从状态图上起点和终点同时开始进行宽度/深度优先搜索,如果发现相遇了,那么可以认为是获得了可行解。这道题,每一个元素会有3种状态,分别是在第一个集合或者第二个集合亦或者不在集合中。如果直接暴力去搜的......
  • P2340 [USACO03FALL] Cow Exhibition G
    [USACO03FALL]CowExhibitionG题目背景题目描述奶牛想证明它们是聪明而风趣的。为此,贝西筹备了一个奶牛博览会,她已经对$N$头奶牛进行了面试,确定了每头奶牛的智商和情商。贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果,所以贝西不希望出展奶牛的智商之......
  • windwos上通过qemu直接开启img、qcow2等格式磁盘镜像(无需转vmdk)
    qemuQEMU(QuickEMUlator)是一款开源的虚拟化软件,能够模拟多种硬件平台,并支持多种虚拟化技术,如KVM(Kernel-basedVirtualMachine)加速。QEMU能够在多个操作系统上运行,包括Windows、Linux和macOS。下载QEMU:访问QEMU官方网站或通过包管理器下载适用于Windows的QEMU......
  • opensatck-dashboard用iso制作qcow2的镜像
    方法上传iso镜像到dashboard创建源为刚上传的ISO的volume创建一个空的volume,后续做系统盘创建一个实例,bootfrom步骤2所创建的volume创建实例挂载卷安装系统删除实例对系统盘的volume使能bootable方式1-dashboard上设置方式2-命令行【cinder命令】命令行修改-【vo......
  • 题解:[USACO07DEC] Sightseeing Cows G
    洛谷P2868题目大意有个nnn个点,mmm条边的有向图,点有点权,边有边......