signed

QiShunwang

“诚信为本、客户至上”

算法学习总结:第二周

2021/3/20 22:50:12   来源:

贪心算法

这周主要学习了贪心算法,学到了很多贪心策略,更深度的了解了贪心的本质:从每个子问题的最优到整体最优。

根据我的学习经验,整理出了一些值得思考与积累的问题

1.排队接水问题

这个题目在上学期的作业5中老师已经布置给我了,那时的我还没有接触算法,并不会用贪心的办法去思考解决,只会模拟暴力求解,最后一直WR……实际上这道题也很简单,只需将每个人的等待时间接到最小的一个水龙头前就行。参考代码:

for(int i=1,j=1;i<=n;i++){
	if(j==r+1)j=1;               //j是水龙头的编号,r是人的个数,i是人的编号
	s[j]+=a[i];                  //第r+1个人返回水龙头
	minx+=s[j];                  //水龙头所用时间加上等待时间
	j++;
}

2.删数问题

给定一个正整数,删去K个数,使剩下的数最小。

这个题目我第一个反应是删去最大的一个数,实则不然,例如1324,删去4得到的132显然比删去3得到的124大。实际上最优的贪心策略是,从左往右遍历删除递增数列的最后一个数。那么为什么这个贪心策略可行呢? 若一个数字比前一个小,那么删除这个数字后面的数显然比删去这个数字前面的数大,因此是完全可行的
参考代码:

while(s!=0)           
    {
        i=0;
        while(n[i]<=n[i+1]) 
        i++;
        while(i<len-1)         //这时已经找到了要取出的数——n[i],这是取出的过程
        {n[i]=n[i+1];i++;}         //其实这个循环可以用erase(i,1);代替
        len--;                //取出后数字长度减1
        s--;                   //消耗掉一次取出次数
    }  

3.上升(或下降)子序列的个数问题

此类问题遇到过多次,像导弹拦截问题,作业中H题等,值得去整理与思考。首先这个命题有另一种等价描述。

下降子序列的个数 == 最长上升子序列的长度
上升子序列的个数 == 最长下降子序列的长度

通过转化求最长上升子序列的长度比较容易,以下提供动态规划和贪心+lower_bound( )二分的方法:
动态规划
时间复杂度为n²

for(int i=1;i<=n;i++){
	for(int j=1;j<i;j++){
		if(a[j]>a[i])dp[i]=max(dp[i],dp[j]+1);
	}
	cnt=max(cnt,dp[i]);
}

贪心+lower_bound( )优化
时间复杂度nlogn

memset(dp,0x3f,sizeof(dp));
for(int i=1; i<=n; i++){
    *lower_bound(dp+1,dp+1+n,a[i])=a[i];//将a[i]插入第一个小于等于它的位置,并且把原有的替换掉
}

dp数组的长度就是最长上升子序列的长度,注意里面的元素不一定是正确的

4.区间调度问题

给定n个活动,其中的每个活动ai包含一个起始时间si与结束时间fi。设计与实现算法从n个活动中找出一个最大的相互兼容的活动子集S。

直接引用贪心策略可能很多人是不太明白的,我们先引入一个命题:

至少存在一个最长事件序列包含最早结束的事件

命题用反正法可以轻松证明。那么贪心策略就显而易见了:按结束时间排序,顺序遍历,如果它与当前已选的所有区间都没有重叠,则选择该区间,否则不选。
参考代码:

sort(a+1,a+1+n);
int t=a[1].y;
for(int i=2;i<=n;i++){
    if(a[i].x>=t){
        cnt++;
        t=a[i].y;
    }
}
cout<<cnt<<endl;

5.最大区间覆盖问题

此类问题涉及较多,例如雷达、喷头灌溉等问题。这些都可以转化为一维区间覆盖问题:
给定一些区间的左右端点,用尽可能少的点覆盖这些区间。

贪心策略1:按端点排序,每次循环更新右端点为此区间与上一个区间的最小值,若左端点比右端点大,则继续,否则额外加一个点

double t=a[1].r,pos=a[1].l,cnt=1;
	for(int i=2;i<=n;i++){
		pos=a[i].l;
		t=min(t,a[i].r);
		if(pos>=t+eps){
			cnt++;
            t=a[i].r;
		}
	}

贪心策略2:按端点排序,不需要每次循环更新右端点,只当该区间大于初始时,更新右端点,每次循环时若左端点比右端点大,则继续,否则额外加一个点并更新端点

	double t=a[1].r,pos=a[1].l,cnt=1;
	for(int i=2;i<=n;i++){
 	      if (t<a[i].l){
 	      cnt++;   
  	      t=a[i].r;     
  	      }       
 	}

6.双指针问题(two points)

此类型的题目有:田忌赛马,分发饼干等等;
贪心策略也是相同的:将大尺寸的饼干分给胃口大的孩子,若最大尺寸的饼干也无法满足,则跳过此孩子

 	sort(g.begin(),g.end(),greater<int>());
    sort(s.begin(),s.end(),greater<int>());
    int res=0, index=0;
    for(int i=0;i<=n;){
        if(index<=n){
            if(g[i]<=s[index]){
                res++;
                index++;     
            }
            i++;
       }
       else break;
    }

7.Protecting the Flowers

有n头奶牛跑到FJ的花园里去吃花了,它们分别在距离牛圈T分钟处吃花,每分钟会吃掉D朵卡哇伊的花儿。FJ现在要将它们给弄回牛圈,但是他每次只能弄一头回去,来回用时总共为2*T分钟,在这段时间内,其它的奶牛会继续吃FJ卡哇伊的花儿,速度保持不变,当然正在被赶回牛圈的奶牛就没口福了!现在要求以一种最棒的方法来尽可能的减少花的损失数量,求奶牛吃掉花的最少朵数!
以前做过类似的题,再次遇到了,就整理下来。
分析:假设序列都由二元组组成,二元组是由D和T组成,那么对一个序列有相邻的两头牛是这样的:
… (a, b) ,(c, d) …
如果(a,b)和(c,d)交换位置了,变成新序列
…(c,d),(a,b)…
假设在这之前FJ已经花了x时间了。
那么赶完这两头牛的损失的量就分别为
x * b + (x + 2 * a) * d
x * d + (x + 2 * c) * b

二者做差
得到ad - bc
若ad < bc 则有第一个序列优于第二个

struct node
{
    int x, y;
    friend bool operator <(const node&a,const node&b){
	return a.x * b.y < a.y * b.x;      //核心排序策略
	}
}a[MAXN];
 sort(a, a+n);
    long long ans=0;
    long long sum=0;
    for(int i=0;i<n;i++){
        ans+=sum*(long long)a[i].y;
        sum+=a[i].x;
    }

8.小船过河问题

只有一艘船,能乘2人,船的运行速度为2人中较慢一人的速度,过去后还需一个人把船划回来,问把n个人运到对岸,最少需要多久。

我第一感觉就是最快的人不断来回将所有人送到对岸,不就是最快的吗?
但实际上,还有一种方法更具竞争力:最快的和次快的过河,然后最快的将船划回来;次慢的和最慢的过河,然后次快的将船划回来。当我们拿笔试几个数时,发现在慢的人与快的人相差较大时,此种方法更优。那么这又是为什么呢???

实际上,当两个慢的人与两个快的人相差较大时,如果用第一种方法,每次运输都可近似为一次慢速度,相当于送两次慢的人;而第二种方法将两个慢的人一起运送,相当于只送一次慢的人!!!如此巧妙!

参考代码:
n<4时单独讨论即可

while(n>3)  
        {  
            sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);  
            n-=2;  
        }  
        if(n==3) sum+=a[0]+a[1]+a[2];  
        else if(n==2) sum+=a[1];  
        else sum+=a[0];  

9.可图性判定

这要属于离散数学的内容了,还没怎么学。不过还是比较简单的。
首先明确两个概念

1.度序列:若把图G所有顶点的度数排成一个序列S,则称S为图G的度序列。
2.序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称该序列是可图的。

Havel-Hakimi定理

由非负整数组成的非增序列S:d1,d2,……,dn(n>=2,d1>=1)是可图的,当且仅当序列S1:d2-1,d3-1,……,dd1+1-1,dd1+2,……dn是可图的。
其中序列S1中有n-1个非负整数,S序列中d1后的前d1个度数(即d2~ dd1+1)减1后构成S1中的前d1个数

参考代码:

sort(k+1,k+1+n);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=i+k[i];j++){
            k[j]--;
            if(k[j]<0){cout<<"NO\n";return;}
        }
        sort(k+1,k+1+n);
    }
    cout<<"YES\n";

学习感悟

这一周学习了不少新的贪心思维,但刷题较少,也需要理解消化,比较忙碌,需要顾及专业课和其他学习内容,但我会尽力平衡关系,合理分配时间,提高专注力与效率。学习之路漫漫,奋斗每一天。