贪心算法初步总结--Farmer John‘s cows_综合

第一周主要介绍了STL的简单应用，STL是一些C++的模板库，它可以使复杂的程序简单化，比如说以前要排序的话要用选择排序法或者冒泡排序法，但是在STL中可以直接用sort()函数实现。再比如说对于可变的字符序列，字符串等，我们可以用string实现，而抛开了原有的char类型。还有map,Multimap,stack,queue,vector,priority_queue,unipue,upper_bound,lower_bound,set,multiset等常用标准模板。STL的功能很多也很强大，对自己的要求是逐渐熟悉它们，并且在以后的不断学习中可以熟练应用，从而提高程序效率并且打开自己的思维。
这一周主要讲了贪心的几大类问题和具体的经典例题。所谓贪心，就是寻找最优解。即按照某种最优策略，将一个复杂的问题分成若干个子问题，将整体的解用局部最优解来等效。是一种比较策略，要进行排序和线性处理，主要还是将一个问题枚举出来找最优解。

以下是对于贪心问题的解决步骤：

1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

贪心分为以下及大类：

1、最优装载问题：重量最轻者最先装；
2、背包问题：既要考虑背包内的物品重量，又要考虑背包内物品的价值。要同时解决这个问题，就要按单位重量价值来判断，即“性价比”问题；
3、货币找零：按照纸币面值的大小排序；
4、区间调度问题：按结束时间最早的排序，以便给下面的活动留出更大的空间，再依次比较开始的时间，从而找出可进行活动的最大数；
5、字典序最小问题：这类问题可以将字符串进行反转处理或则将字符串从中间分开存到两个数组中，即two point 双指针问题；
6、分发饼干问题：将饼干和孩子的胃口值分别降序排列并进行反向处理；
7、小船过河问题：寻求两组情况的最优值。

Eg:Farmer John‘s cows

题意：n个牛站一排，每头牛更其他牛都要讲话，讲话有声音，
声音大小和距离有关。问，n头牛同时和其他牛讲话时所有分贝。

解题思路：相邻一段间的距离被利用的次数为左边的牛数右边的牛数2，
这样对每一段累加就好了，其实是把每一种情况的每一步的每一区间
都拆开了。

//错误解法：超时

#include
#include
#include
#define IOS ios::sync_with_stdio(false);
typedef long long ll;
using namespace std;int main()
{
     IOS;
ll n,i,j,s=0;
ll a[10010];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
for(j=0;j<n;j++){
    if(a[i]-a[j]>=0)s+=a[i]-a[j];elses+=a[j]-a[i];}cout<<s<<endl;}

//AC：将超时的代码中的计算问题用一个数学公式进行简化

 #include
#include
#include
#define IOS ios::sync_with_stdio(false);
typedef long long ll;
using namespace std;int main()
{
     IOS;
ll n,i,s=0,t=0;
ll a[10010];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=1;i<n;i++){
    t=(a[i]-a[i-1])*i*(n-i)*2;s+=t;}cout<<s<<endl;}

学习贪心算法中主要遇到的不足：

1.对于局部最优不一定是全局最优的题就不要用贪心。
2.事实上条件能符合贪心的题不多，要多加分析，不然就会做错或者做不出来。

在以后的学习中，要不断去开阔自己的思维，不能仅仅局限于课堂，或者说是已经AC的题目，一个题目AC的方法有很多，要不断去借鉴和学习多种思路，落于实践，才能形成一种好的思维，才能在以后的题目中快速看出是那一大类的贪心，该类贪心又如何解决。还要将问题的方面考虑全面，不要漏解。
Origi！！！