今天我写写贪心算法（上），主要写写一些题目和方法。
很高兴的借（fu）鉴（zhi）、选（kao）取（bei）了一些。
贪心算法的定义：
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。
此外，贪心常用sort排序，来取一些最大值。
当然，不是猜完就能用的，一定要证明[哈哈]。
常用题目：①背包问题，其实属于dp动态规划。
②活动安排问题，按结尾从小到大排序，尽量挑开始符合结束时间的。
题目：1319：【例6.1】排队接水
题目缩略：
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
思路：简单的数学问题。最快的最先来接水，先排序，后面一个一个来。
代码：
#include <bits/stdc++.h>
using namespace std;
struct nbdj
{
int num,t;
} a[10005];
int n,ts,m;
double ans;
bool cmp(nbdj a,nbdj b)
{
if(a.t!= b.t)return a.t<b.t;
return a.num<b.num;
}
int main()
{
cin>>n;
m=n;
for(int i=1; i<=n; i++)
{
cin>>a[i].t;
a[i].num=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1; i<=n; i++)
{
cout<<a[i].num<<" ";
ts+=a[i].t*(n-i);
}
ans=ts*1.0/n;
printf("\n%.2lf\n",ans);
return 0;
}
题目：1320：【例6.2】均分纸牌(Noip2002)、
题目：
有n堆纸牌，编号分别为 1，2，…, n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为1的堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 n 的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 n=4，4堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从 ③ 取4张牌放到④（9 8 13 10）->从③取3张牌放到 ②（9 11 10 10）-> 从②取1张牌放到①（10 10 10 10）。
思路：从左到右，如果缺，从右边要，如果多，给右边
代码：
#include <bits/stdc++.h>
using namespace std;
int a[250],n,ans,num;
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
num+=a[i];
}
num/=n;
for(int i=1; i<=n; i++)
{
a[i]-=num;
}
int i=1;
while(a[i]==0&&i<=n) i++;
while(i<=n)
{
if(a[i]!=0)
{
a[i+1]+=a[i];
ans++;
}
i++;
}
cout<<ans<<endl;
return 0;
}
好勒，今天就写到这，明天再写，日更完成。明天似乎有4到贪心题要写。不过也没事，都做好了，明天见。
