点击查看《Cookies》题解详情

附件1、解法1-dfs 程序填空

#include <bits/stdc++.h>
using namespace std;

const int N = ___;                 // 最大孩子数 
___ INF = 1e18;       // 无限大值，用于初始化最小怨气 

int n, m;               // 孩子数、饼干总数 
int g[___], idx[___];   // g[i]：孩子i的贪婪度；idx[i]：排序后第i个孩子的原始索引 
int c[___];            // 当前分配方案，c[i]表示排序后第i个孩子分到的饼干数 
int best_c[___];       // 最优分配方案 
long long min_anger = ___; // 最小怨气总和 

bool cmp(int a,int b) {
	return ___;
}

/*
* 深度优先搜索枚举所有可能的分配方案 
* pos：当前正在分配的孩子位置（排序后的索引）
* remaining：剩余的饼干数 
* current_anger：当前已经产生的怨气（只考虑前pos-1个孩子）
*/
void dfs(int pos, int remaining, long long current_anger) {
	// 如果所有孩子都已分配且饼干刚好用完，检查是否找到更优解 
	if (pos == ___) { //得到一种分配方案
		if (remaining == ___ && current_anger ___ min_anger) {
			___                    // 更新最小怨气 
			for (int i = 1; i <= n; ++i) ___; // 保存最优分配方案 
		}
		___
	}
	
	// 确定当前孩子饼干数的上限：
	// 1. 不能超过剩余饼干数（因为后面每个孩子至少1块饼干，所以剩余饼干数必须至少为n-pos）
	// 2. 为了保持分配序列非递增（这是最优解的性质），不能超过前一个孩子的饼干数（如果pos>1）
	int max_val = ___; // 至少给后面每个孩子留 1 块饼干 
	if (pos > 1) max_val = min(___, ___); // 非递增约束 
	
	// 枚举当前孩子的饼干数（从大到小枚举，有助于更快找到较优解）
	for (int val = ___; val >= 1; --val) {
		c[pos] = ___; // 尝试分配 val 块饼干给当前孩子 
		
		// 计算当前孩子的怨气：统计前 pos-1 个孩子中饼干数大于 val 的数量 
		int a_i = ___;
		for (int j = 1; j < pos; ++j) {
			if (___) ___;
		}
		long long new_anger = ___ + 1LL * ___;
		
		// 如果新怨气已经超过当前最优解，剪枝，不再继续搜索 
		if (___) ___;
		
		// 递归搜索下一个孩子，剩余饼干数减少val，怨气更新为new_anger 
		dfs(___, ___, ___);
	}
}

int main() {
	freopen("Cookies.in", "r", stdin);
	freopen("Cookies.out", "w", stdout);
	cin >> n >> m; // 输入孩子数和饼干总数
	
	// 输入每个孩子的贪婪度 
	for (int i = 1; i <= n; ++i) {
		cin >> g[i];
		idx[i] = ___; // 记录原始索引 
	}
	
	// 将孩子按贪婪度降序排序（存在最优解使得分配序列与贪婪度降序对应）
	sort(idx ___, idx ___, ___);
	
	// 将贪婪度数组按照排序后的顺序重新排列，便于搜索时使用 
	int sorted_g[N];
	for (int i = 1; i <= n; ++i) {
		sorted_g[i] = ___;
	}
	memcpy(g, sorted_g, sizeof(sorted_g));
	
	// 开始深度优先搜索 
	dfs(___, ___, ___);
	
	// 输出最小怨气总和 
	cout << min_anger << endl;
	
	// 将最优分配方案还原到原始孩子顺序 
	int final_ans[N];
	for (int i = 1; i <= n; ++i) 
		final_ans[___] = ___;
	
	// 输出每个孩子分到的饼干数
	for (int i = 1; i <= n; ++i) {
		cout << ___ << " ";
	}
	cout << endl;
	
	return 0;
}

附件2、解法1-dp 程序填空

#include <bits/stdc++.h>
using namespace std;

const int N = ___;                 // 最大孩子数
const int M = ___;               // 最大饼干数
const long long INF = ___;       // 无穷大，用于初始化DP

struct Child {
	int id;                      // 原始编号
	long long g;                 // 贪婪度
} children[___];                   // 存储孩子信息

int n, m;                        // 孩子数量和饼干总数
long long g[___];                  // 排序后的贪婪度数组
long long prefixSum[___];          // 贪婪度前缀和，用于快速计算区间和
long long dp[___][___];              // DP数组：dp[i][j]表示前i个孩子分配j块饼干的最小怨气

// 记录转移路径的结构体
struct Path {
	int type;                    // 转移类型：0-整体加一，1-新增层级
	int param;                   // 参数：type=0 时无用，type=1 时表示层级长度
	int prev_i, prev_j;          // 前一个状态
} path[___][___];

int allocation[___];               // 最终分配方案（排序后的顺序）
int originalAns[___];              // 最终分配方案（原始顺序）

/**
 * 比较函数：按贪婪度降序排序
 * 原理：根据交换论证，最优解中贪婪度大的孩子饼干数不少于贪婪度小的孩子
 * 所以我们可以将孩子按贪婪度降序排序，然后只考虑非递增的分配方案
 */
bool compareChildren(___ a, ___ b) {
	return ___;
}

/**
 * 功能：回溯构造分配方案
 * i 当前孩子数
 * j 当前饼干数
 *
 * 从最终状态(n, m)开始回溯：
 * 1. 如果是从整体加一转移过来的，说明前 i 个孩子的饼干数都加了 1
 * 2. 如果是从新增层级转移过来的，说明最后 param 个孩子饼干数设为 1
 */
void reconstruct(int i, int j) {
	// 记录每个孩子的基础饼干数（1或0）
	vector<int> base(___, ___);
	// 记录每个孩子额外加的饼干数（通过整体加一操作）
	vector<int> add(___, ___);

	// 从最终状态开始回溯，直到处理完所有孩子
	while (___) {
		Path p = path[___][___];

		if (___) { // 类型0：整体加一转移
			// 说明当前状态是通过给前 i 个孩子每人加一块饼干得到的
			// 所以给前 i 个孩子的 add 值都加 1
			for (int ___) {
				add___;
			}
		} else { // 类型1：新增层级转移
			// 说明最后 p.param 个孩子（从 i-p.param+1 到 i）饼干数设为 1
			int len = ___;
			for (int t = ___; t <= ___; t++) {
				base[t] = ___;  // 这些孩子的基础饼干数为 1
			}
		}
		// 回溯到前一个状态
		i = p.___;
		j = ___
	}
	// 合并基础值和额外值，得到最终分配方案
	for (int t = 1; t <= n; t++) allocation[t] = ___
}

int main() {
//	freopen("Cookies.in", "r", stdin);
//	freopen("Cookies.out", "w", stdout);
	// 输入孩子数量和饼干总数
	cin >> n >> m;
	if (m % n == 0) {//特殊情况
		___
		return 0;
	}

	// 输入每个孩子的贪婪度
	for (int i = 1; i <= n; i++) {
		cin >> children[i].___;
		children[i].id = ___;  // 记录原始编号
	}
	/****************************************************************
	 * 第一步：按贪婪度降序排序
	 *
	 * 为什么需要排序？
	 * 1. 根据交换论证，最优解中贪婪度大的孩子饼干数不少于贪婪度小的孩子
	 * 2. 排序后，我们可以假设分配序列是非递增的，大大减少搜索空间
	 * 3. 这样我们只需要考虑满足 c[1] >= c[2] >= ... >= c[n] 的方案
	 ****************************************************************/
	sort(___, ___, ___);
	// 提取排序后的贪婪度，并计算前缀和
	for (int i = 1; i <= n; i++) {
		g[i] = ___;
		prefixSum[i] = ___;
		// prefixSum[i] = g[1] + g[2] + ... + g[i]，用于快速计算区间和
	}
	/****************************************************************
	 * 第二步：动态规划初始化
	 *
	 * dp[i][j] 表示前 i 个孩子（排序后）分配 j 块饼干的最小怨气
	 * 初始状态：
	 *   dp[0][0] = 0: 0 个孩子分配 0 块饼干，怨气为 0
	 *   其他状态设为无穷大，表示不可达
	 ****************************************************************/
	for (int i = ___; i <= ___; i++) {
		for (int j = ___; j <= ___; j++) dp[i][j] = ___; //状态初始化
	}
	dp[___][___] = ___; //边界状态
	/****************************************************************
	 * 第三步：动态规划状态转移
	 *
	 * 考虑两种情况：
	 * 1. 整体加一转移（对应所有孩子饼干数都大于1）
	 *    如果给前 i 个孩子每人加一块饼干，怨气不变
	 *    转移：dp[i][j] = dp[i][j-i] (前提：j >= i)
	 *
	 * 2. 新增层级转移（对应最后 len 个孩子饼干数为 1）
	 *    设最后 len 个孩子饼干数为 1，前面 i-len 个孩子饼干数大于 1
	 *    这 len 个孩子每人都会产生怨气：每个孩子前面有 (i-len) 个孩子饼干数多于他
	 *    总怨气增加：(i-len) * (g[i-len+1] + ... + g[i])
	 *    转移：dp[i][j] = min{ dp[i-len][j-len] + (i-len)*(sum[i]-sum[i-len]) }
	 *
	 * 其中len从 1 到 i，表示最后一个层级（饼干数为 1）的孩子数量
	 ****************************************************************/
	for (int i ___) { //阶段
		for (int j ___) {  // j 至少为 i，因为每人至少一块饼干
			// 情况1：整体加一转移
			// 如果 j>=i，说明可以从前 i 个孩子每人少一块饼干的状态转移过来
			if (j ___ i && dp[i][___] ___ dp[i][j]) {
				dp[i][j] = dp[___][___];
				path[i][j] = {0, 0, ___, ___};  // 记录转移路径
			}

			// 情况2：新增层级转移
			// 枚举最后一个层级的长度 len（即饼干数为 1 的孩子数量）
			for (int len = ___; len <= ___; len++) {
				if (j >= ___) {  // 确保有足够的饼干
					// 计算新增的怨气
					// (i-len) 是前面饼干数大于 1 的孩子数量
					// (prefixSum[i] - prefixSum[i-len]) 是最后 len 个孩子的贪婪度之和
					long long newAnger = dp[___][___] + (___) * (prefixSum[___] - prefixSum[___]);

					if (newAnger ___ dp[i][j]) {
						dp[i][j] = ___;
						path[i][j] = {___, ___, ___, ___};  // 记录转移路径
					}
				}
			}//for len
		}//for j
	}//for i
	/****************************************************************
	 * 第四步：输出最小怨气
	 *
	 * dp[n][m] 就是前 n 个孩子（所有孩子）分配 m 块饼干的最小怨气
	 ****************************************************************/
	cout << ___;

	/****************************************************************
	 * 第五步：回溯构造分配方案
	 *
	 * 通过记录的转移路径，从最终状态(n, m)开始回溯，构造出具体的分配方案
	 * 有两种类型的转移：
	 * 1. 整体加一：给前i个孩子每人加一块饼干
	 * 2. 新增层级：最后len个孩子饼干数设为1
	 ****************************************************************/
	reconstruct(n, m);

	/****************************************************************
	 * 第六步：将排序后的分配方案映射回原始顺序
	 *
	 * 因为我们是按贪婪度降序排序后进行的DP和方案构造
	 * 所以需要将分配方案映射回原始的孩子顺序
	 ****************************************************************/
	for (int i = 1; i <= n; i++) {
		// children[i].id 是排序后第 i 个孩子的原始编号
		// allocation[i] 是排序后第 i 个孩子分到的饼干数
		originalAns[___] = ___;
	}
	// 输出每个孩子的饼干数（按原始顺序）
	for (int ___) cout << ___ << " ";
	___
	return 0;
}