acwing 算法基础课(第六章完整版 c++详解)

2024-04-13 06:04

本文主要是介绍acwing 算法基础课(第六章完整版 c++详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 六、贪心

(一).区间问题

考虑按左端点或右端点或双端点排序

1.AcWing 905.区间选点

(1)算法思想:

        先将每个区间按照右端点从小到大排序吗,然后从小到大依次枚举每一个区间,如果当前右端点已经包含在该区间内,则跳过这个区间,否则更新右端点为当前区间的右端点。

        证明:比较最终结果ans和选出的点个数cnt大小关系,即证ans>=cnt&&cnt>=ans。

先证ans<=cnt:由于上述方法选择的方案保证了每一个区间都至少包含一个点,因此为一个合法的方案,而ans表示的是合法方案中的最少点个数,因此ans<=cnt。

再证ans>=cnt:考虑没有被跳过的区间,区间互不相交,因此选中cnt个区间,要想覆盖所有区间,最终的答案一定至少为cnt个点(因为区间是独立的),即ans>=cnt。得证。

(2)代码实现思路:

        设置一个区间含义的结构体,即包含左端点和右端点,结构体以右端点大小作为排序依据。然后排序该结构体。初始化选择的右端点为负无穷,选择的点的数量为0从小到大枚举每一个区间,如果当前区间的左端点大于选择的右端点,则更新右端点为当前区间的右端点,并将选择点的数量加1。

(3)代码实现:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
struct Range
{int l,r;bool operator< (const Range &W)const{return r<W.r;}
}range[N];
int n;
int main()
{// 3// -1 1// 2 4// 3 5cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;range[i]={l,r};}sort(range,range+n);int res=0,st=-2e9;for(int i=0;i<n;i++)if(range[i].l>st){res++;st=range[i].r;}cout<<res;return 0;
}

2.AcWing 908.最大不相交区间数量

(1)算法思想:

        与上题思路一致,但求的是最大的不相交区间数量。

        证明:比较最终结果ans和选出的区间个数cnt大小关系,即证ans>=cnt&&cnt>=ans。

先证ans>=cnt:由于选出的区间各不相交,因此为合法的方案,而ans为所有合法方案中最大的一个,因此有ans>=cnt。

再证ans<=cnt:运用反证法,假设ans>cnt,cnt表明每个区间都至少有一个选好的点,而ans表示所有不相交的区间的数量,说明至少应该有ans个点才能使每一个区间都有一个点,产生矛盾,因此ans<=cnt

(2)代码实现思路:

        与上题代码一致

(3)代码实现:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
struct Range
{int l,r;bool operator< (const Range &W)const{return r<W.r;}
}range[N];
int n;
int main()
{// 3// -1 1// 2 4// 3 5cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;range[i]={l,r};}sort(range,range+n);int res=0,st=-2e9;for(int i=0;i<n;i++)if(range[i].l>st){res++;st=range[i].r;}cout<<res;return 0;
}

3.AcWing 906.区间分组

(1)算法思想:

        先按照区间左端点对所有区间排序,然后按照左端点从小到大枚举所有区间,再枚举所有的集合,如果当前区间的左端点小于每个集合当中的最大右端点max_r,就说明该区间不能放入任何一个现有的集合当中,因此要重新开辟一个集合再放入该区间;若当前区间的左端点大于某一集合的右端点,则说明可以该区间与该集合不产生冲突,因此可以将该区间放入该集合当中,并更新当前组的max_r。(注意若满足可以放入的条件,可以挑选任意一个集合放入,因此可以使用小根堆

        证明:ans表示最终的答案,cnt表示按照上面的思路得到的组的个数

先证ans<=cnt:由于按照上述方法选出的组的个数是一个合法方案,而ans是所有合法方案中的最小值,因此有ans<=cnt。

再证ans>=cnt:考虑当新加入的区间与之前的所有组Cnt-1都产生冲突的情况,即需要新开辟一个组,此时这cnt个组都包含1个公共点li,因此合法方案至少要包含这cnt个组,因此ans>=cnt。

(2)代码实现思路:

        设置一个小根堆记录所有组的右端点,再对所有区间按照左端点的大小排序。按照区间左端点从小到大枚举每一个区间,若堆为空或者堆顶小于当前区间的左端点,说明当前区间与所有组都产生冲突,因此需要将该区间的右端点加入堆中,否则说明该区间至少可以加入堆顶的组中,因为该区间的右端点一定大于堆顶,因此通过删除堆顶再加入该区间的右端点即可更新堆顶组。最终输出堆的元素个数。

(3)代码实现:

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N=100010;
struct Range
{int l,r;bool operator <(const Range &W)const{return l<W.l;}
}range[N];
int n;
int main()
{// 3// -1 1// 2 4// 3 5cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;range[i]={l,r};}sort(range,range+n);priority_queue<int ,vector<int> ,greater<int> > heap;for(int i=0;i<n;i++){if(heap.empty()||heap.top()>=range[i].l) heap.push(range[i].r);else{heap.pop();heap.push(range[i].r);}}cout<<heap.size();
}

4.AcWing 907.区间覆盖

(1)算法思想:

        先按照区间左端点对所有区间排序,然后按照左端点从小到大枚举所有区间。选择能覆盖起点的右端点最大的区间,然后更新起点为所选区间的右端点。

        证明:cnt为每个方案的区间数量,ans为最终答案。

先证ans<=cnt:由于每一个按照上面方法所选的方案一定合法,而ans是在所有合法方案中选择一个最小的,因此有ans<=cnt。

再证ans>=cnt(ans=cnt):对于任意最优解,可以通过替换最优解方案中与上面方法得到的方案不一样的区间,使得最优解转化为上述方法得到的方案,因此ans=cnt。

(2)代码实现思路:

        利用双指针算法找到左端点小于起点并且右端点最大的区间,即令j等于当前枚举的区间,初始化右端点为负无穷,用j来枚举i之后并且左端点小于当前起点的所有区间,取最大的右端点。如果最大的右端点都在起点的左侧,则说明无解,跳出循环,若有解,则将所选区间数量加1,如果最大的右端点已经超过终点,则说明已经选好最优方案。再更新起点为最大的右端点,最后更新i=j-1。若最后没有找到方案则输出-1,否则输出区间个数。

(3)代码实现:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
struct Range
{int l,r;bool operator <(const Range &W)const{return l<W.l;}
}range[N];
int n,st,ed;
int main()
{// 1 5// 3// -1 3// 2 4// 3 5cin>>st>>ed;cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;range[i]={l,r};}sort(range,range+n);int res=0;bool success=false;for(int i=0;i<n;i++){int j=i,r=-2e9;while(j<n&&range[j].l<=st){r=max(r,range[j].r);j++;}if(r<st) break;res++;if(r>=ed){success=true;break;}st=r;i=j-1;}if(!success) cout<<-1;else cout<<res;return 0;
}

(二).Huffman树

1.AcWing 148.        合并果子

(1)算法思想:

        把所有果子都放进小根堆里,每次取权值最小的两个果子合并成一个果子,然后再放进小根堆对,依此类推,直到堆中只存在一个果子,该权值就是答案。

        证明:先验证第一步的正确性,即若最小的两个果子不在树的最底部,则交换最深的果子和权值最小的果子,如下图,假如a,f为最小的果子,那么交换b,f,交换后的答案一定比原答案小(因为越深算的次数越多)。

        再验证之后每一步按照该操作后,整体仍然为最小答案。设最初状态为f(n),则下一个状态为在合并最小的两个果子后的方案即f(n-1),可以得到f(n)=f(n-1)+a+b,因此去掉最小两个果,合并成一个果考虑的最优情况等同于初始态减去最小两个果,因此下一步就只需要考虑n-1个点,再合并最小两个果经过上面的验证是整体最优方案,依此类推每一步合并最小两个果就是整体最优。

(2)代码实现思路:

        无

(3)代码实现:

        

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{int n;priority_queue<int ,vector<int>,greater<int>> heap;cin>>n;while(n--){int x;cin>>x;heap.push(x);}int res=0;while(heap.size()>1){int a,b;a=heap.top(),heap.pop();b=heap.top(),heap.pop();res+=a+b;heap.push(a+b);}cout<<res;return 0;
}

(三).排序不等式

1.AcWing 913.排队打水

(1)算法思想:

        由题意可知假设有7个人,每个人打水时间为ti(i=1 2..7),第一个人不用等,但他让后面每一个人都等了t1时间,第二个人让他后面每一个人都等了t2个时间...依次类推,最后一个人打水时间对总等待时间没贡献,因此有6t1+5t2+4t3+3t4+2t5+1t6+0t7,容易得到打水耗时越少的越再前面,这样总等待时间最小。

        证明:假设后面某一个人的打水时间小于前面某一个人的打水时间ti>tj(i<j),通过公式可以发现只有在包含ti,tj与我们推测的最小情况的公式不同,因此将两项作差发现我们推测的方案时间更少。

(2)代码实现思路:

        无,注意最终答案可能会溢出,因此用long long来存。

(3)代码实现:

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int n,t[N];
int main()
{
//7
//3 1 2 5 4 6 7cin>>n;for(int i=0;i<n;i++) cin>>t[i];LL res=0;sort(t,t+n);for(int i=0;i<n;i++) res+=t[i]*(n-i-1);cout<<res;return 0;
}

(四).绝对值不等式

1.AcWing 104.        货仓选址

(1)算法思想:

        先对所有点从小到大排好序,猜测使得所有点到该仓库的距离最小的货仓位置在所有点的中间点,若为偶数则中间两个点选谁都可以。

        证明:先写出总距离的函数,再两两一组考虑,即将第一个点和最后一个点放在一起,对于该组而言,有|x1-x|+|xn-x|>=xn-x1,显然货仓的位置要在两点之间的任意位置才是这两个点到货仓距离的最小值,最小值为xn-x1,依次类推将该函数每一组都放缩成两点相减的形式,因此有f(x)>=xn-x1+xn-1-x2+...,我们要找到的点就是使得f(x)等于右侧的情况,显然该点要在每一组的内部,因此该点应该在中间点,得证。

(2)代码实现思路:

        累加每个点到中间点的距离的绝对值即可。

(3)代码实现:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int n,a[N];
int main()
{// 4// 6 2 9 1cin>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);int res=0;for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);cout<<res;return 0;
}

(五).推公式

1.AcWing 125.         耍杂技的牛

(1)算法思想:

        按照每头牛强壮值加上重量从小到大排序,此时最大的风险值最小。

        证明:choice表示按照上面方法计算出的最大的风险值,res表示所有方案中最小的风险值

        先证choice>=res:由于choice为所有方案中的一种,而res是所有方案的最小值,因此choice>=res。

        再证choice<=res:假设最终结果中出现不是从小到大排序的两头牛,那么交换这两头牛使得该方案成为排好序的方案,经过计算发现结果会变小即变得更优(见下图1,经化简后变为图2),因此有res>=choice。得证。

(2)代码实现思路:

        定义一个pair类型数组cow[],存储w+s,w,然后对cow排序(默认按照第一个位置w+s排序),然后枚举每一头牛,s=cow.first-w,w=cow.second,然后取该牛的强壮值减去它上面所有牛的重量和res的最大值赋值给res,再将每一头牛的重量累加。最后输出res。

(3)代码实现:

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=50010;
PII cow[N];
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){int w,s;cin>>w>>s;cow[i]={w+s,w};}sort(cow,cow+n);int sum=0,res=-2e9;for(int i=0;i<n;i++){int w=cow[i].second,s=cow[i].first-w;res=max(res,sum-s);sum+=w;}cout<<res;return 0;
}

这篇关于acwing 算法基础课(第六章完整版 c++详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/899318

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig