【贪心算法】算法训练 ALGO-1003 礼物（C/C++）

贪心算法（Greedy Algorithm) 概述：

贪心算法是一种在求解最优化问题时采取的一种常用算法策略。贪心算法的基本思想是，每次选择当前情况下的局部最优解，并相信这个局部最优解能够导致全局最优解。贪心算法通过迭代的方式一步步地构建最优解，并不进行回溯，贪心主要就是每一步的最优必然导致最终结果的最优。

贪心算法的一般步骤：

1. 将问题分解成多个子问题，比如最短路保证每一步自己走的是最低的； 2. 对每个子问题，确定一个最优解（局部最优）； 3. 对每个子问题的最优解进行合并，得到原问题的最优解（全局最优）。

贪心算法的正确性需要满足两个条件：

1.最优子结构：问题的最优解能够由子问题的最优解组合而成。 2. 贪心选择性：通过局部最优选择能够得到全局最优解。

贪心算法适用的问题一般具有以下特点：

1. 子问题的最优解能够推导出原问题的最优解； 2. 子问题的最优解构成原问题的最优解时，原问题的最优解也能由它推导出。

贪心算法的优点是简单、高效，时间复杂度通常较低。然而，贪心算法并不适用于所有问题，有些问题需要使用其他更复杂的算法来求解。在使用贪心算法时，需要仔细分析问题的特点并证明贪心策略的正确性。

算法训练 ALGO-1003 礼物

资源限制 内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s 问题描述 　　JiaoShou在爱琳大陆的旅行完毕，即将回家，为了纪念这次旅行，他决定带回一些礼物给好朋友。 　　在走出了怪物森林以后，JiaoShou看到了排成一排的N个石子。 　　这些石子很漂亮，JiaoShou决定以此为礼物。 　　但是这N个石子被施加了一种特殊的魔法。 　　如果要取走石子，必须按照以下的规则去取。 　　每次必须取连续的2*K个石子，并且满足前K个石子的重量和小于等于S，后K个石子的重量和小于等于S。 　　由于时间紧迫，Jiaoshou只能取一次。 　　现在JiaoShou找到了聪明的你，问他最多可以带走多少个石子。 输入格式 　　第一行两个整数N、S。 　　第二行N个整数，用空格隔开，表示每个石子的重量。 输出格式 　　第一行输出一个数表示JiaoShou最多能取走多少个石子。 样列输入 　　8 3 　　1 1 1 1 1 1 1 1 样列输出 　　6 样列解释 　　任意选择连续的6个1即可。 数据规模和约定 　　对于20%的数据：N<=1000 　　对于70%的数据：N<=100,000 　　对于100%的数据：N<=1000,000，S<=10^12，每个石子的重量小于等于10^9，且非负

解题思路：

本题我们讲解的为贪心算法，此题的贪心我们可以理解为每一次的取石子（局部最优）导致最后的最多取多少石子（全局最优），我们把取石子分为每一步取得石子来看，只要保证了每一步的最优便可以使结果最优。在取石子时有很多限制条件，排列成一排我们可以理解为前缀和的思想处理，这样在计算石子的时候更快，在判断k为几时，我们的二分便可以倾巢而动了，用二分查找判断k，再利用一个check函数判断是否符合题意即可。

AC代码：

#include<stdio.h>
long long sum[1000005];//计算前缀和
//a[n]  :a[1]         a[2]        a[3]        ...  a[n]
//sum[n]:sum[0]+a[1]  sum[1]+a[2] sum[2]+a[3] ...  sum[n-1]+a[n]
long long a[1000005];
long long s,n;
int fun(int k) {//判断条件是否成立，
	int i;
	for (i=k;i<=n-k;i++) {
		if (sum[i]-sum[i-k]<=s&&sum[i+k]-sum[i]<=s)
        //当i=k时，计算的是0~2k；当i=n-k时，计算的是n-2k~n
        //把为2*k长度连续的区间遍历一遍，判断是否成立
			return 1;//成立返回1，
	}
	return 0;//不成立返回0，
}
int main() {	
	scanf("%lld%lld",&n,&s);
	int i;
	sum[0]=0;
//sum[0]不真正算入其中，避免对sum[i] = sum[i - 1] + a[i]讨论，若i=0，则无sum[-1]
	for (i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	int left =1;
	int right =n;
	int k = 0;
//1-n,已经是排好的连续序列
//利用二分查找，把连续的数组不断分成两部分，查找其中一部分，若不存在缩小范围一半，继续查找
	while (left <= right) {
		int mid = (left + right) / 2;
		if (fun(mid)==1) {
			left = mid + 1;//若找到则改变left,寻求最大的k(范围给到右区间)
			k = mid;

		}else{
			right = mid - 1;//找不到说明k太大，无法满足条件，去左区间找
		}
	}
	printf("%d",2*k);
	return 0;//要加return 0;否则会判错（蓝桥判题）
}

注：本人小白一枚，注释可能有许多不正确的地方，还请各位大佬指点。共同学习进步。小编做此题时，经历了 不懂题 理解错题 遗漏情况的过程，现把我理解错题的思路说一下，希望各位避坑，首先，取2*k个不一定从头开始去，比如2 1 1 1 1 1 1 2 3，n=9,k=3;可以从第二个开始取，这样可以取6个最多。