《算法设计与分析》（一）枚举：基本思想+问题优化+应用实例

枚举算法，也称之为穷举算法，就是按照问题本身的性质，一 一列举出该问题所有可能的解，并在列举的过程中，逐一检验每个可能解是否是问题的真正解。若是则采纳这个解；否则抛弃它。

• 不能遗漏，否则可能导致结果不正确
• 不能重复，否则可能导致效率降低

• 枚举算法的解准确和全面
• 实现简单，通过循环/递归实现
• 执行效率提升空间往往比较大

1. 确定枚举对象：枚举对象也可以理解为文体街的表达形式，一般需要若干参数 (p1,p2,…,pk)来描述。
2. 逐一列举可能解：根据枚举对象的参数构造循环，一一列举其表达式的每一种取值情况。
3. 逐一验证可能解 根据问题解的要求，一一验证枚举对象表达式的每一个取值，如果满足条件，则采纳它，否则，抛弃之。

• 优化模型 针对问题特征，优化对象模型
• 优化过程 针对对象特征，优化列举和验证过程

给你一个长度为n的数组A和一个正整数k，问从数组中任选两个数使其和是k的倍数，有多少种选法。对于数组a1=1 , a2=2 , a3=2而言：
(a1,a2)和(a2,a1)被认为是同一种选法；
(a1,a2)和(a1,a3)被认为是不同的选法。

第一行有两个正整数n，k。n<=1000000，k<=1000 第二行有n个正整数，每个数的大小不超过1e9

选出一对数使其和是k的倍数的选法个数

#include
#include
using namespace std;

#define LL long long
int n,k;
int a[10001];

void init() {
	memset(a,0,sizeof(a));
	cin>>n>>k;
	for(int i=0; i> t;
		a[t%k]++; //对每个出现的数 先取余 %k  再计数
	}
}
void work() {
	LL ans=0;
	for(int i=0; i 
实例2 移除石头 
题目描述 
 
 
有一条河，河中间有一些石头，石头的数量以及相邻两块石头之间的距离已知。现在可以移除一些石头，假设最多可以移除m块石头（注意：首尾两块石头不可以移除，且假定所有的石头都处于同一条直线）。
 问最多移除m块石头后相邻两块石头之间的最小距离的最大值是多少？
 
 
这里解释一下“最小距离的最大值”：就是移除后，每相邻之间的石头之间的距离的最大值
 
输入 
 
 
多组输入（<=20组数据，读入以EOF结尾）
 每组第一行输入两个数字：n(2<=n<=1000)为石头的个数，m(0<=m<=n-2)为可移除的石头数目，随后n-1个正整数，表示顺序相邻两个石头的距离d(d<=1000)。
 
 
输出 
 
 
每组输出一行结果，表示最大值。
 
 
分析 
 
这里显然用简单的贪心策略是行不通的
 如对于 n=5,m=2 , 顺序相邻两个石头的距离序列为：4-1-3-2 ，贪心的话，我们会选择距离最小的位置去移除石头，那么就是去掉1-3 和 3-2之间的石头。此时移除后的解为4。
 但，可以分析出，当我们移掉4-1和1-3之间的石头时，移除后的解为2。
 
 
求满足条件 C(d) 的 最大值 d，其中C(d)描述为：
 C(d)≔ 最多移除m个石头后 任意 相邻两个石头的距离 不小于d
 
 
代码 
#include
#include
using namespace std;

int a[1005],dis[1005]= {0};
int n,m;

int Validate(int d) { //找满足条件的最大的d    最多移除m个石头后任意相邻两个石头的距离不小于d
	int k=m; //可以移除的石头的数目
	int st=1;//表示最初的石头
	for(int en = 2 ; en<=n ; ) { //表示最末（当前）的石头
		int dis_cur = dis[en]-dis[st];//st与en石头间距 
		while(dis_cur < d) { //移除第en个石头
			k--;//移除
			en++;//考虑下一个石头
			if(k<0) //移除的石头多了
				return 0;
			if(en>n) {
				if(st == 1) //第1和第n块（实际最后的一个）石头之间的距离小于d
					return 0;
				return 1;//可以把st移除 与前面一个区间合并满足条件。
			}
			dis_cur=dis[en]-dis[st];//更新距离
		}
		st=en;//更新起始点
		en++;//当前的en 已经在“while(dis_cur < d)”考虑了 还要再次更新一下
	}
	return 1;
}
int main() {
	while(cin>>n>>m);
	for(int i=2; i<=n; i++) {
		cin>>a[i]; //a[i]表示两石头i-1~i 间的距离
		dis=a[i]+dis[i-1];//dis[i]表示从头到第i个石头间的距离
	}
	//二分查找
	int l=0,r=1000*1000 +5;
	while(l Ans)
//			Ans = dist;
//		return ;
//	}
//	Flag[t]=1;
//	recursiveEnum(t+1);
//	Flag[t]=0;
//	recursiveEnum(t+1);
//}