算法(一) : 贪心_给出n,求n的所有表示方案中,拆分出的数字的乘积最大的方案,

算法(一) : 贪心

介绍

     从今天开始，就会有 [ 算法 ] 这么一个系列了，本系列将以C++为例，
     以后还会有“数论”“图论”等系列。
1
2

小引

     所谓“ 贪心” 就是把任务转换成一个系统化的问题，可以通过一系列推算得
     出一个策略来得出最优解。
     尽管这种方法后续可以用dp和DFS替换掉，但是也是一种相当重要的解题的
     方法。
1
2
3
4

贪心的理解

   通常来说，我们可以通过一系列推论来导出这么一个策略.
1

例题1 最大乘积：

  		题目描述
		一个正整数n可以表示为若干个正整数之和，给出 n，求所有表示方
		案中，拆分出的数字的乘积最大的方案，如果乘积一样，输出拆分
		的数字最多的方案，按升序依次输出拆分出的数字。

		样例1输入
		6
		样例1输出
		3 3
		样例2输入
		8
		样例2输出
		2 3 3
1
2
3
4
5
6
7
8
9
10
11
12
13

有兴趣的小伙伴们可以停下来思考。

例题1 题解：

		不难推断出应当尽量多拆3出来：
				若前面的乘积是a，则可以用动态规划的思想，在和为3时，
				拆成3是最划算的，再向后推导，发现当和为任意一个质
				数时（拆成合数必能再分解），拆成尽可能多的3和几个
				2就可以使乘积最大，此处不再赘述。所以当且仅当拆完
				后n==4 || n==2时拆出2
1
2
3
4
5
6

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000001];
bool cmp(int m,int b){
	return m<b?1:0;
}
int main(){
	int n;
	scanf("%d",&n);
	int cnt=0;
	while(n>4){
		a[++cnt]=3;
		n-=3;
	}
	if(n==4){
		a[++cnt]=2;
		a[++cnt]=2;
	}else if(n==3){
		a[++cnt]=3;
	}else if(n==2){
		a[++cnt]=2;
	}else if(n==1){
		a[++cnt]=1;
	}
	sort(a+1,a+1+cnt,cmp);
	for(int i=1;i<=cnt;i++)
		printf("%d ",a[i]);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
'
运行
运行

这是一道比较入门的题，类似的还有什么性价比最高呀等等，不再赘述，再多来几道题体验一下：

例题2 过河问题：

	河边有一只小船，小船最多能容纳3人。有n个人想要过河，
	每个人都拥有一个属性：划船时间t。
	
	如果船上只有1人，那么只需要1人划船，小船从河的一岸
	到另一岸所需时间为划船者i的划船时间t[i]。
	如果船上有不少于2人，那么需要2人划船，小船从河的一
	岸到另一岸所需时间为2个划船者i,j的划船时间的较大值 
	max(t[i],t[j])。
	
	小船过河后，必须有人将它划回来，以载下一批人过河。
	不计上下船所需时间，求 n人全部过河的最短时间。
1
2
3
4
5
6
7
8
9
10
11

例题2 题解：

	是不是觉得这道题有点水平呀，让我来告诉你：
	0.排序
	为了便于后续贪心的分析过程，这里首先
	要对所有时间 ti 按照升序做排序处理：
	t1 ≤ t2 ≤ · · · ≤ tn
	1.基本推论
		1.1 推论一
			以下均假设船最初在左岸。
			从左岸到右岸的船一定是满载 3 人的，这是因为如果只载 1 人，
			那么还需要人把船划回来，这一次划船就没有意义；如果载 2 
			人，不如再顺便捎带一个人，因为捎带的这个人不会影响过河
			时间。
		1.2 推论二
			从右岸到左岸的人数可能是 1 人或 2 人。
			如果回来 1 个人，那么肯定是让划船最快的那个人回来；如果
			回来 2 个人，那么肯定是让划船最快的两个人回来。这是因为，
			如果选取了任意划船更慢的人回来，那么他将来还必须得再划
			回去，不如直接让划船最快的人回来，这样答案肯定不会更差。
		1.3 推论三
			综合以上推论，本题的最优过河模式只有两种。
			第一种是 t1 带两个人过河，t1 回来；第二种是 t1, t2 带一个人
			过河，t1, t2 回来。每一轮过河一定是这两个模式其中选一个。
			这同时也说明，除了 t1, t2，其余人一	旦过河就不能再回来了。
	
	2.详细分析
		2.1 直观分析
			两种过河模式有什么区别呢？
			初步分析一下，如果 t2 相对于剩下的人划船都比较快，那么
			采用双人摆渡模式（t1, t2带一个人过河，t1, t2 回来），虽然
			摆渡次数会增加，但是单次摆渡的时间会节省很多；如果 t2 
			和剩下的人划船速度差不多，那么就没必要让 t2 来参与摆渡，
			而是要选用单人摆渡模式（t1 带两个人过河，t1 回来），因
			为这时候摆渡次数增加量带来的时间增加已经抵消掉了单次
			摆渡时间的减少量，所以直接让 t1 单人摆渡就行。
			
			*本题的贪心思路基本可以确定了：先让 t1 和 t2 双人摆渡，
			把那些划船最慢的人按顺序送走，直到某个时候双人摆渡不
			再具有优势，这时候 t1 单人摆渡把剩下的人送走。
			
			那么要如何确定这个界限呢？
		2.2 数学分析
			考虑 t1 ≤ t2 ≤ ti ≤ tj 这 4 个人中的 t1, tj 要过河的情况。
			方案一：单人摆渡
				1.t1, ti, tj 过河，时间为 ti；
				2. t1 回来，时间为 t1。
			总时间为 t1 + ti。
			
			方案二：双人摆渡
				1. t1, t2, tj 过河，时间为 t2；
				2. t1, t2 回来，时间为 t2。
				3. t1, t2, ti 过河，时间为 t2；
				4. t1, t2 回来，时间为 t2。
				总时间为 4t2。
				
			比较与结论
				采取单人摆渡而不采取双人摆渡的条件是：
					4t2 > t1 + ti
						也就是说，如果满足这个条件，单人摆渡就比
						双人摆渡要划算。这就是两个方案之间的分界线。
						最终的方案是：t2 到 ti 这 i − 1 个人是最终要参与
						双人摆渡和 t1 搭档划船的人，他们可以再捎带 i−1 
						个人。除了这 2i−1 个人以外的其他人，就得靠 t1, 
						t2 双人摆渡先带过河。
		2.3 特殊情况
			如果 2i − 1 ≥ n，说明所有人都要靠 t1 单人摆渡送过去，如果 
			n 为奇数则每次过河都是 3 人满载，但 n 为偶数时，如果按这
			个方案去执行会发现有一次过河只有 2 人上船，造成船不满载
			的效率损失。
			此时，要分析两种情况：
				1. 保持方案不变，每次都是 t1、左岸剩下的人中最快
				的一个、左岸剩下的人中最慢的一个过河，最后一次只有 t1 带 t[n/2+1]
				二人过河，总共花费 t1 + t2 + · · · + t[n/2+1]
				2.t1、t2 先把 tn 运过河，之后一起回来，人数变为奇数，可以
			正常的每次都 3 人满载过河。可以推出：当 t1 + t[n/2]> 2t2 时采用后一种方案更优。这是需要特判的一个情况.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

太长了。。。上代码！

#include<cstdio>
#include<iostream>
#include<algorithm>
int a[2003];
int n,ans=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	std::sort(a+1,a+1+n);
	int p=0;
	for(int i=n;i>=1;i--){
		if(4*a[2]>a[1]+a[i]){
			p=i;
			break;	
		}
	}
	if(2*p-1>=n){
		if(n%2==0&&a[1]+a[n/2+1]>2*a[2]){
			ans+=2*a[2];
			n--;	
		}
		for(int i=2;i<=n/2+1;i++)
			ans+=a[1]+a[i];
		ans-=a[1];	
	}else{
		ans+=2*a[2]*(n-(2*p-1));
		for(int i=2;i<=p;i++)
			ans+=a[1]+a[i];
		ans-=a[1];
	}
	printf("%d\n",ans);	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

好啦，一切有关贪心的基础就讲完啦！接下来，我们将会接触一种方法：
”临项交换“

例题3 狂暴的老师：

样例1输入
3
5 1
1 4
2 2
样例1输出
2

例题3 狂暴的老师 题解：

临项交换，很大程度上会和数论有关，再此不赘述，最多用到的是max，min的取值。
我们假设将两人排列交换，就得到一个新的序列，再按题目要求算出不同的答案的项，
判断两个项的大小，就得到答案：
				(a[i].t+a[i].p>a[j].t+a[j].p)时 (用冒泡排序，
				这里的j>i)时，交换序列
			然后再求出答案。
1
2
3
4
5
6

给出代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n;
struct stu{
	int t,p;
}a[1009];
void qswap(int x,int y){
	stu tmp=a[x];
	a[x]=a[y];
	a[y]=tmp;
	return;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].t,&a[i].p);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i].t+a[i].p>a[j].t+a[j].p){
				qswap(i,j);
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		printf("%d %d\n",a[i].t,a[i].p); 
//	} 
	int ans=-a[1].p,sum=a[1].t;
	for(int i=2;i<=n;i++){
		ans=max(ans,sum-a[i].p);
		sum+=a[i].t;
		
	}
	printf("%d",ans);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

那么还有一些其他的求最值的题目，只需要你去找到题目中在序列结尾，开头或其它不变的量，通过简单的分析：得出定论，再写下代码。

方法 solution & 小结 Summary：

在求最值时可用贪心找寻到一定策略解题：
1.手算小数据
2.推理基本性质
3.由基本性质推导出高阶性质
4.暴力求解后可适当优化：
1
2
3
4
5

为了解释第四点，于是特意准备一道题：

 求序列的最大子段和：
 		我们发现若加上a[j] ，ans”变为“负数，于是一定不是最优解，又
 		推出一定不能加上第j项，因为一定不是最优，由此：
 			在枚举左端点和右端点的基础上，如此优化：
1
2
3
4

#include <cstdio>
int a[1000001];
int n;
long long ans = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int flag;
    for (int i = 1; i <= n; i = flag) {
        long long sum = 0;
        for (int j = i; j <= n; j++) {
            flag = j + 1;
            if (sum + a[j] < 0)
                break;
            sum += a[j];
            if (sum > ans)
                ans = sum;
        }
        if (flag > n)
            break;
    }
    printf("%lld", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

特别鸣谢：

oj.7fa4.cn