贪心算法 求解思路

贪心算法简介

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时（看起来是）最佳的选择。这种启发式策略并不是总能产生出最优解，但它常常能给出最优解。

在实际设计贪心算法时，通常直接做出贪心选择来构造子结构，以产生一个待优化解决的子问题，或者，根据贪心选择来构造最优子结构。

贪心算法的一般做法

虽然贪心算法没有固定的解题模板，但一般情况下使用贪心算法，需要对问题进行分析，可以参考下面的解题步骤；

1. 问题定义：明确问题的输入、输出和目标。

2. 状态定义：**将问题分解为多个阶段，每个阶段都有一个状态。**状态通常由问题的某些属性表示。（如取最大值或者最小组等）

3. 确定贪心策略：在每个阶段，根据当前状态选择最优决策，以期望达到全局最优解。这个最优决策通常是最优子结构的一部分，问题的最优解可以通过其子问题的最优解来获得，则问题具有最优子结构，这意味着每个阶段的最优决策都是全局最优解的一部分。

4. 代码实现：根据上述步骤设计贪心算法，编写代码。通常，贪心算法包括一个循环，每次循环中都选择当前最优决策，并更新状态。

5. 算法分析：分析贪心算法的正确性和可行性。

贪心算法实例

下面演示的题目来自 洛谷P1080 国王游戏的题目, 其问题的求解的核心就是拆解问题，将问题分为小问题，并且取局部最优解。本题涉及的内容包括 贪心算法+高精度的变换。

求解思路：

代码：

#include<bits/stdc++.h>
using namespace std;
struct temp{
	int l,r,all;
}a[1005];
bool cmp(temp a,temp b){
	return a.all<b.all;
}
int main(){
	int n;
    int result = 0;
	cin>>n;
	for(int i=0;i<=n;i++){
		cin>>a[i].l>>a[i].r;
		a[i].all=a[i].l*a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	int sum=1;
	for(int i=1;i<=n;i++){
		sum*=a[i-1].l;
        if(sum/a[i].r > =result){
        result = sum / a[i].r;
        }
	}
	cout<<result;
	return 0;
}

测试情况如下所示，可以看到在不考虑高精度的情况也是得分能达到60分，故此在平时做题时，当涉及到贪心算法的应用时，需要将问题进行拆解细分为小问题，并且运用数学逻辑将问题简答化（建议采用假设方法）。

正确AC解法：

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

 struct stu {
     int l;  // 大臣的左手数
     int r;  // 大臣的右手数
 } f[1005];  // 定义结构体数组 f，最多可容纳 1005 位大臣
 
 // 比较函数，用于排序
 bool cmp(stu a, stu b) {
     return a.l * a.r < b.l * b.r;  // 按左手数和右手数的乘积升序排序
 }
 
 int n;  // 大臣数量
 vector<int> ans(1, 0);  // 初始化答案向量，初始值为 0
 vector<int> t(1, 1);  // 初始化乘积向量，初始值为 1
 
 // 高精度数乘法
 inline vector<int> mul(vector<int> &a, int b) {
     vector<int> res;  // 存储结果的向量
     int t = 0;  // 进位
     int len = a.size();  // 输入向量的长度
     for (int i = 0; i < len; i++) {
         t += a[i] * b;  // 乘以 b
         res.push_back(t % 10);  // 取当前位
         t /= 10;  // 更新进位
     }
     while (t) {  // 处理剩余的进位
         res.push_back(t % 10);
         t /= 10;
     }
     return res;  // 返回乘法结果
 }
 
 // 高精度数除法
 inline vector<int> div(vector<int> &a, int b) {
     vector<int> res;  // 存储结果的向量
     int r = 0;  // 余数
     int len = a.size();  // 输入向量的长度
     for (int i = len - 1; i >= 0; i--) {  // 从低位到高位处理
         r = 10 * r + a[i];  // 将当前位加入余数
         if (r >= b) {  // 如果余数大于等于除数
             res.push_back(r / b);  // 计算商并存入结果
             r %= b;  // 更新余数
         } else {
             res.push_back(0);  // 商为0
         }
     }
     vector<int> cnt;  // 存储结果的向量（逆序）
     len = res.size();
     for (int i = len - 1; i >= 0; i--) {
         cnt.push_back(res[i]);  // 逆序存取结果
     }
     // 去掉前导零
     while ((cnt.back() == 0) && (cnt.size() > 1)) {
         cnt.pop_back();
     }
     return cnt;  // 返回除法结果
 }
 
 // 比较两个高精度数
 inline int compare(vector<int> &a, vector<int> &b) {
     int lenA = a.size();
     int lenB = b.size();
     if (lenA != lenB) {  // 长度不同
         return lenA - lenB;  // 返回长度差
     } else {  // 长度相同
         for (int i = lenA - 1; i >= 0; i--) {
             if (a[i] != b[i]) {  // 从高位比较
                 return a[i] - b[i];  // 返回差值
             }
         }
         return 0;  // 相等
     }
 }
 
 int main() {
     cin >> n;  // 输入大臣数量
     cin >> f[0].l >> f[0].r;  // 输入国王的左手数和右手数
     for (int i = 1; i <= n; i++) {  // 输入每位大臣的左右手数
         cin >> f[i].l >> f[i].r;
     }
     sort(f + 1, f + 1 + n, cmp);  // 按照比较函数排序大臣
 
     t = mul(t, f[0].l);  // 将国王的左手数乘入乘积
     for (int i = 1; i <= n; i++) {  // 遍历每位大臣
         vector<int> res = div(t, f[i].r);  // 计算当前大臣的金币数
         if (compare(ans, res) < 0) {  // 如果当前金币数更大
             ans = res;  // 更新结果
         }
         t = mul(t, f[i].l);  // 更新乘积，乘入当前大臣的左手数
     }
 
     int len = ans.size();  // 获取结果的长度
     for (int i = len - 1; i >= 0; i--) {  // 输出结果（逆序）
         cout << ans[i];
     }
     cout << endl;  // 输出换行
     return 0;  // 返回成功
 }