Adding Solutions

Basic Debugging

Choosing a Language

Contest Strategy

Contests

Contributing

C++ With the Command Line

Data Types

How to Debug

Debugging C++

Expected Knowledge

Fast Input & Output

(Optional) C++ - Writing Generic Code

Input & Output

Introduction to Competitive Programming

(Optional) C++ - Lambda Expressions

Resources: Learning to Code

Introducing Modules

Olympiads

How to Practice

Resources: Competitive Programming

Resources: USA-Specific

Running Code Locally

Running Code Online

USACO Camp

USACO FAQs

USACO Monthlies

Using This Guide

Working With MDX

Ad Hoc Problems

Casework

Complete Search with Recursion

Additional Practice for USACO Bronze

Basic Complete Search

Introduction to Data Structures

Introduction to Graphs

Introduction to Greedy Algorithms

Introduction to Sets & Maps

Introduction to Sorting

Rectangle Geometry

Simulation

Time Complexity

Binary Search

Binary Search on a Sorted Array

Additional Practice for USACO Silver

Flood Fill

Introduction to Functional Graphs

Graph Traversal

Greedy Algorithms with Sorting

Intro to Bitwise Operators

Introduction to Tree Algorithms

More on Prefix Sums

Introduction to Prefix Sums

Priority Queues

Custom Comparators and Coordinate Compression

Two Pointers

DP on Trees - Solving For All Roots

Combinatorics

Additional Practice for USACO Gold

(Optional) Sorted Sets with Custom Comparators

Bitmask DP

Range DP

DP on Trees - Introduction

Disjoint Set Union

Digit DP

Divisibility

Hashing

(Optional) Hashmaps

Introduction to DP

More Operations on Sorted Sets

Knapsack DP

(Optional) LCA with Euler Tour

Longest Increasing Subsequence

Minimum Spanning Trees

(Optional) Meet In The Middle

Modular Arithmetic

Point Update Range Sum

Paths on Grids

Shortest Paths with Non-Negative Edge Weights

Sliding Window

Stacks

Optimizing Unimodal Functions

Topological Sort

(Optional) Euler Tour Technique

Shortest Paths with Unweighted Edges

2D Range Queries

Binary Jumping

(Optional) Bitsets

Centroid Decomposition

Additional Practice for USACO Platinum

Convex Hull

Convex Hull Trick

Divide & Conquer - DP

Divide & Conquer - SRQ

Sum over Subsets DP

Geometry Primitives

Heavy-Light Decomposition

Matrix Exponentiation

Small-To-Large Merging

Inclusion-Exclusion Principle

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
 const _components = {
 a: "a",
 code: "code",
 h2: "h2",
 h3: "h3",
 li: "li",
 ol: "ol",
 p: "p",
 pre: "pre",
 strong: "strong",
 ...props.components
 }, {CPPSection, FocusProblem, HeaderLink, JavaSection, LanguageSection, MATHSPAN, Problems, PySection, Spoiler} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!FocusProblem) _missingMdxReference("FocusProblem", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!JavaSection) _missingMdxReference("JavaSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 if (!Problems) _missingMdxReference("Problems", true);
 if (!PySection) _missingMdxReference("PySection", true);
 if (!Spoiler) _missingMdxReference("Spoiler", true);
 return _jsxs(_Fragment, {
 children: [_jsx(_components.p, {
 children: "分类讨论题可以拆分成若干种情况，再分别求解每一种情况。"
 }), "\n", _jsx(_components.p, {
 children: "这类题通常需要画出大量情况，并观察每一种情况的特点。"
 }), "\n", _jsx(_components.p, {
 children: "我们可以尝试找出不同情况之间的相似之处，从而用同一种方法解决其中多种情况。"
 }), "\n", _jsx(FocusProblem, {
 problem: "case-tutorial"
 }), "\n", _jsxs(_components.h2, {
 id: "解答sleepy-cow-herding",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#解答sleepy-cow-herding",
 children: _jsx(HeaderLink, {})
 }), "解答——Sleepy Cow Herding"]
 }), "\n", _jsxs(Spoiler, {
 title: "解答",
 children: [_jsx(_components.p, {
 children: "我们分别求最少和最多移动次数。下文把奶牛所在的位置称为“元素”；如果两个元素\n之间没有其他元素，就称它们相邻。"
 }), _jsxs(_components.h3, {
 id: "最少移动次数",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#最少移动次数",
 children: _jsx(HeaderLink, {})
 }), "最少移动次数"]
 }), _jsx(_components.p, {
 children: "最少移动次数分为三种情况："
 }), _jsxs(_components.ol, {
 children: ["\n", _jsx(_components.li, {
 children: "三个元素已经连续。"
 }), "\n", _jsx(_components.li, {
 children: "有两个相邻元素之间恰好空着一个位置。"
 }), "\n", _jsx(_components.li, {
 children: "不满足上述两种条件的其他情况。"
 }), "\n"]
 }), _jsxs(_components.p, {
 children: ["第一种情况下，元素已经连续，因此答案为 ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "0",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>0</mn></mrow><annotation encoding=\"application/x-tex\">0</annotation></semantics></math>0"
 }), "。"]
 }), _jsxs(_components.p, {
 children: ["第二种情况下，答案为 ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "1",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>1</mn></mrow><annotation encoding=\"application/x-tex\">1</annotation></semantics></math>1"
 }), "，因为只需把孤立的元素移入另外两个元素之间的空位。"]
 }), _jsxs(_components.p, {
 children: ["第三种情况下答案为 ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "2",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>2</mn></mrow><annotation encoding=\"application/x-tex\">2</annotation></semantics></math>2"
 }), "。对于任何其他测试用例，最优做法都是把最小元素移到\n", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\max-2",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>max</mi><mo>⁡</mo><mo>−</mo><mn>2</mn></mrow><annotation encoding=\"application/x-tex\">\\max-2</annotation></semantics></math>max−2"
 }), "，或把最大元素移到 ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\min+2",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>min</mi><mo>⁡</mo><mo>+</mo><mn>2</mn></mrow><annotation encoding=\"application/x-tex\">\\min+2</annotation></semantics></math>min+2"
 }), "，这样就转化为了第二种情况。"]
 }), _jsxs(_components.h3, {
 id: "最多移动次数",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#最多移动次数",
 children: _jsx(HeaderLink, {})
 }), "最多移动次数"]
 }), _jsx(_components.p, {
 children: "最多移动次数一定是有限的，因为每次操作都会让两个端点之间的距离（下文称为\n“跨度”）至少减少一。为了最大化移动次数，最佳方法是把每个元素放到尽可能靠近\n某个端点、但自身不成为端点的位置。移动一次后，跨度将等于两个相邻元素之间的\n最大距离；此后的每次移动都会使跨度减一，直到跨度变为二。因此，最多移动次数\n等于相邻元素间的最大距离减一。"
 }), _jsxs(_components.h2, {
 id: "实现",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#实现",
 children: _jsx(HeaderLink, {})
 }), "实现"]
 }), _jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "时间复杂度："
 }), " ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(1)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><mn>1</mn><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(1)</annotation></semantics></math>O(1)"
 })]
 }), _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <algorithm>\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint main() {\n\tfreopen(\"herding.in\", \"r\", stdin);\n\tfreopen(\"herding.out\", \"w\", stdout);\n\n\tvector<int> a(3);\n\tfor (int &b : a) { cin >> b; }\n\tsort(a.begin(), a.end());\n\n\t/*\n\t * The minimum number of moves can only be 0, 1, or 2.\n\t * 0 is if they're already consecutive,\n\t * 1 is if there's a difference of 2 between any 2 numbers,\n\t * and 2 is for all other cases.\n\t */\n\tif (a[0] == a[2] - 2) {\n\t\tcout << 0 << endl;\n\t} else if ((a[1] == a[2] - 2) || (a[0] == a[1] - 2)) {\n\t\tcout << 1 << endl;\n\t} else {\n\t\tcout << 2 << endl;\n\t}\n\n\t// max is equal to largest difference between end and middle, minus one.\n\tcout << max(a[2] - a[1], a[1] - a[0]) - 1;\n}\n"
 })
 })
 }), _jsx(JavaSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-java",
 children: "import java.io.*;\nimport java.util.*;\nclass Main {\n\tpublic static void main(String[] args) throws IOException {\n\t\tScanner sc = new Scanner(new File(\"herding.in\"));\n\t\tPrintWriter pw = new PrintWriter(new File(\"herding.out\"));\n\t\tint[] cows = new int[3];\n\t\tcows[0] = sc.nextInt();\n\t\tcows[1] = sc.nextInt();\n\t\tcows[2] = sc.nextInt();\n\t\tArrays.sort(cows);\n\n\t\t/*\n\t\t * The minimum number of moves can only be 0, 1, or 2.\n\t\t * 0 is if they're already consecutive,\n\t\t * 1 is if there's a difference of 2 between any 2 numbers,\n\t\t * and 2 is for all other cases.\n\t\t */\n\t\tif (cows[2] == cows[0] + 2) {\n\t\t\tpw.println(0);\n\t\t} else if (cows[1] == cows[0] + 2 || cows[2] == cows[1] + 2) {\n\t\t\tpw.println(1);\n\t\t} else {\n\t\t\tpw.println(2);\n\t\t}\n\n\t\t// max is equal to largest difference between end and middle, minus one.\n\t\tpw.println(Math.max(cows[1] - cows[0], cows[2] - cows[1]) - 1);\n\t\tpw.close();\n\t}\n}\n"
 })
 })
 }), _jsx(PySection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-py",
 children: "with open(\"herding.in\", \"r\") as file_in:\n\ta, b, c = map(int, file_in.readline().split())\n\n\"\"\"\nThe minimum number of moves can only be 0, 1, or 2.\n0 is if they're already consecutive,\n1 is if there's a difference of 2 between any 2 numbers,\nand 2 is for all other cases.\n\"\"\"\nif c == a + 2:\n\tminimum = 0\nelif b == a + 2 or c == b + 2:\n\tminimum = 1\nelse:\n\tminimum = 2\n\n# max is equal to largest difference between end and middle, minus one.\nmaximum = max(b - a, c - b) - 1\n\nprint(f\"{minimum}\\n{maximum}\", file=open(\"herding.out\", \"w\"))\n"
 })
 })
 })]
 })]
 }), "\n", _jsxs(_components.h2, {
 id: "题目",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#题目",
 children: _jsx(HeaderLink, {})
 }), "题目"]
 }), "\n", _jsx(Problems, {
 problems: "casework"
 })]
 });
}
function MDXContent(props = {}) {
 const {wrapper: MDXLayout} = props.components || ({});
 return MDXLayout ? _jsx(MDXLayout, {
 ...props,
 children: _jsx(_createMdxContent, {
 ...props
 })
 }) : _createMdxContent(props);
}
return {
 frontmatter,
 default: MDXContent
};
function _missingMdxReference(id, component) {
 throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it.");
}

Video Solution