题意分析

题目描述了一个由南北向和东西向的平行河流组成的网格系统。直升机需要巡查所有的河流段，以检测牛奶是否变酸。目标是找到一条最短的飞行路径，使得直升机能够覆盖所有的河流段，并且飞行的总距离最短。飞行成本与飞行距离成正比，因此需要最小化总飞行距离。 具体输入包括： $1$.$n$条南北向的河流和$e$条东西向的河流。

$2$.第二行给出$n-1$个整数，表示相邻南北向河流之间的距离（从东到西的顺序）。

$3$.第三行给出$e-1$个整数，表示相邻东西向河流之间的距离（从北到南的顺序）。 输出是最小的飞行距离（即最小成本）。

解题思路

$1$. 问题建模​：将河流网格看作一个图，南北向和东西向的河流的交点就是图的顶点。直升机需要覆盖所有的边（河流），即这是一个“边覆盖”问题。由于河流是直线且平行，可以简化为覆盖所有行和列的河流。

$2$. ​最小生成树（MST）​​：实际上，这个问题类似于构建一个网格的最小生成树。直升机需要从一个起点出发，经过所有河流的最短路径。对于网格图，最小生成树的总权重是行和列的最小生成树的结合。

$3$. 贪心策略​：为了覆盖所有河流，我们需要选择连接所有行和列的最小路径。具体来说：

$(1)$对于南北向的河流，我们需要n-1个垂直连接（东西向的跨越）。

$(2)$对于东西向的河流，我们需要e-1个水平连接（南北向的跨越）。

$(3)$每次选择当前最小的未连接的边（距离最小的行或列间隔） $4$. Kruskal算法​：将所有的行间隔和列间隔排序，然后从小到大选择n-1和e-1个最小的间隔，总和即为最小飞行距离。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

class GraveyardDesign {
private:
	ll num;
	vector<vector<ll>> solutions;
	
	void saveSolution(ll left, ll right) {
		vector<ll> solution;
		solution.push_back(right - left + 1); // 区域数量
		for (ll i = left; i <= right; ++i) {
			solution.push_back(i); // 区域边长
		}
		solutions.push_back(solution);
	}
	
public:
	void setNum(ll n) {
		num = n;
		solutions.clear();
	}
	
	void findSolutions() {
		ll left = 1, right = 1;
		ll sum = 0;
		
		while (true) {
			// 扩展右边界直到sum >= num
			while (sum < num && right <= 1e7) {  // 1e7是足够大的上限
				sum += right * right;
				++right;
			}
			
			if (sum < num) break; // 无法再找到更大的和
			
			if (sum == num) {
				saveSolution(left, right - 1);
			}
			
			// 移动左边界
			sum -= left * left;
			++left;
		}
	}
	
	void printSolutions() {
		// 按区域数量从大到小排序
		sort(solutions.begin(), solutions.end(), 
			[](const vector<ll>& a, const vector<ll>& b) {
				return a[0] > b[0];
			});
		
		cout << solutions.size() << "\n";
		for (const auto& sol : solutions) {
			for (size_t i = 0; i < sol.size(); ++i) {
				cout << sol[i];
				if (i != sol.size() - 1) cout << " ";
			}
			cout << "\n";
		}
	}
};

int main() {
	GraveyardDesign solver;
	ll num;
	
	while (cin >> num) {
		solver.setNum(num);
		solver.findSolutions();
		solver.printSolutions();
	}
	
	return 0;
}