0x07 贪心

贪心的证明手段：（主要是说给自己听的）

1）微扰（临项交换）

对局部最优形成的解进行的任何调整都会让整体结果变坏

通常要结合冒泡排序的知识：任何一个序列都可能通过临项交换的方法达到有序序列

2）范围缩放

3）决策包容性

在任何局面下，作出局部最优决策后，之后可达的集合包含了其他决策之后可达的集合，简而言之就是“不亏”。以奶牛晒太阳为例，x，y都能拿，在这种情况下我拿y更优，因为拿y未来的可行状态包含了拿x的所有可行状态。

4）反证法

5）数学归纳法

例题1：奶牛晒太阳


可以看到本题简化后就是：给定了一堆区间[Li,Ri]，和N个点，求最多的满足要求的区间数目

思路一：按照L进行降序，每次选择当前奶牛能用的最大的SPF防晒霜。正确性证明：如果有两瓶不同的可以选择的SPF[x]<SPF[y]，下一头奶牛只会出现3种情况：

1）x、y均能用

2）x、y均不能用

3）x能用，y不能用

可见当前奶牛选用y是更好的

此外，如果当前奶牛放弃日光浴，这瓶防晒霜给别的另一头奶牛用，那么对于（除了这两头奶牛外的）其他奶牛来说，效果是等价的。所以当前防晒霜给这头奶牛用不会让结果更差。

小知识STL：priority_queue默认是大根堆，小根堆可以用负号实现。

小根堆维护最小值，大根堆维护最大值。

例题2：雷达安装


这里从建筑出发，对于每一个建筑来说，给定了一个监控在数轴上的区间范围。将这些区间按照L排序，每次维护当前监控的在数轴上的最右侧的可能位置pos：

​ 如果Li大于pos，那就新建一个监控并令pos=Ri

​ 否则pos=min（pos，Ri）

同样使用“决策包容性”证明：

​ 对于每个区间[Li, Ri]，有两种选择：1）使用已有的监控；2）新建一个监控

​ 如果选择使用已有的监控，那么未来可以在任意位置新建一个监控；反之如果直接选择新建一个监控，那么这个监控就不能在任意位置。显然前者“不亏”（包含了后者的未来可行状态）

例题3:国王游戏（经典的“微扰法”贪心例题）

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，
使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

这里很重要的一点是“微扰”转变为整个序列的有序：其实一个序列的排序规则就是由相邻两数的偏序关系决定的（且这个偏序关系必须有传递性）例如x<y,y<z可以推到x<z，那么这个序列也就唯一确定了

以这题为例，要求相邻两数按照左手*右手小的排在前面，且就 “左手*右手“ 这个规则来说（此时不要求相邻），是有传递性的：L1*R1, L2*R2, L3*R3

附：传送门：皇后游戏 https://www.cnblogs.com/Miracevin/p/9694887.html

例题4：给树染色


错误的贪心：每次选择权值最大的染色。（反例：如果有一个父节点的A[i]很小，它有许多权值巨大的儿子，那么它的儿子们会安排在最后选）

但是可以发现，当前状态下权值最大的节点一定会在它的父节点染色后被立刻染色。如果有三个节点x,y,z，x,y是连续染色的，那么就有以下两种情况：

• x,y,z：x+2y+3z
• z,x,y：z+2x+3y

要比较这两种情况做差可以得到

如果(x+y)/2>z，那么选方案一；反之选方案二

也就是相当于两个节点：(x+y)/2 与 z 谁大先选谁

那么我们就可以将这两个点合并，并且儿子的孩子也归为父亲，3个点就变成了2个点，最后所有的点就会合并为一个点。

如何计算最后的结果呢？

有两种方法：

1）合并后的节点记录它内部点的顺序

2）在每次合并后，ans+=被合并的点的值，被合并的点的父亲值=(值+被合并的点的值)/集合点数。

原理是父亲的值要算1次，而这个点的值要算两次。

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using  namespace std;
struct node{
	int c,num,id;
	double p;
	node (int id=0,int c=0,int num=1,double p=0):id(id),c(c),num(num),p(p){}
}a[2010];
bool operator<(node x,node y){return x.p<y.p;}
multiset<node> S;
vector<int> son[2010];
int fa[2010];
void init(int n){
	for (int i=1;i<=n;i++) son[i].clear();
	S.clear();
}
int main(){
	ios::sync_with_stdio(false);
//	freopen("1","r",stdin);
	while (true){
		long long ans=0;
		int n,r;cin>>n>>r;
		if (n==0) break;
		init(n);
		for (int i=1;i<=n;i++){
			cin>>a[i].c;
			a[i].id=i;
			a[i].num=1;
			a[i].p=a[i].c;
			S.insert(a[i]);
		}
		for (int i=1;i<=n-1;i++){
			int father,son1;cin>>father>>son1;
			fa[son1]=father;
			son[father].push_back(son1);
		}
		
		for (int i=1;i<=n-1;i++){
			typedef multiset<node>::iterator it;
			it p=--S.end();
			if (p->id==r) p--;
			node father,current;
			current=*p;
			S.erase(p);//删除儿子
			for (it si=S.begin();si!=S.end();si++){
				if (si->id==fa[p->id]){
					father=*si;
					S.erase(si);//删除父亲
					break;
				}
			}
			for (vector<int>::iterator j=son[father.id].begin();j!=son[father.id].end();j++)
				if (*j==current.id){
					son[father.id].erase(j);
					break;
				}
			for (int j=0;j<son[current.id].size();j++){
				int y=son[current.id][j];
				fa[y]=father.id;//current的儿子的父亲是father
				son[father.id].push_back(y);//current的儿子加入父亲
			}
			
			S.insert(node(father.id,father.c+current.c,father.num+current.num,1.0*(father.c+current.c)/(father.num+current.num)));
			ans+=current.c*father.num;
		}
		cout<<ans+S.begin()->c<<endl;
	}
	return 0;
}