贪心算法笔记

贪心算法笔记

大概内容

贪心就是对于一个问题有很多个步骤，我们在每一个步骤中都选取最优的那一个，最后得出答案。就是在一些函数中可行，但是有些比如二次函数，因为它的转折点不一定最优，就是不可行的。那么如何判断贪心呢？有这么几种

• 看时间复杂度，一般的就是 $O(n)$ 或者是排序 $O(nlogn)$​
• 或者猜测，看着像就可以试试。
• 自己用数学证明方法，比如归纳法，交换法，就是如果交换之后答案变得小或者大就可以了。

那贪心在比赛中怎么办呢？可以先尝试一下大小样例，再尝试对拍，有个保底，如果可以也可以证明一下。

然后还有一种贪心，叫做反悔贪心，就是可以撤销，也没别的。

最后因为贪心每次取局部最优，所以代码不长，而且时间复杂度不大。

例题讲解

凌乱的yyy / 线段覆盖

题目大意:有 $n$ 个线段，问最多有多少个不重叠的线段。

思路：贪心，然后按照 $r_i$ 排序，每次选取尽可能早的场次并且要合法，也就是不能前面重叠。

证明：如果不相交，那么图片如下。

很明显，一场弄完，另一场。如果包含，图片如下：

那样我们就可以选择第一场，因为它结束得早，可以取另外的场次。所以证明取更早的是永远比更晚的要更优。

时间复杂度：$O(n\log n)$

#include<bits/stdc++.h>
struct noip//有同学不会结构体的多开几个数组 
{int begin;//开始时间 int finish;//结束时间 
}a[2000005];
bool cmp(noip x,noip y)
{return x.finish<y.finish;//按结束时间排 
}
using namespace std;
int main()
{int n,ans=1;//初始化 cin>>n; for(int i=1;i<=n;i++){cin>>a[i].begin>>a[i].finish;}sort(a+1,a+n+1,cmp);//快速排序(不用我多说了吧) int mini=a[1].finish;//定义mini统计最后结束时间 int j=1;while(j<=n)//我用了while,感兴趣的同学可以用for(提示：for不用定义j) {j++;if(a[j].begin>=mini)//新的比赛开始时间要晚于mini {ans++;//统计比赛数 mini=a[j].finish;//更新mini }}cout<<ans<<endl;//输出 return 0;//功德圆满 
}

Teleporters (Easy Version)

思路：直接 $a_i+i$ 排序，就好了。

证明：就是每次都是走过去，传回来，所以直接排序就可以了。

时间复杂度：$O(n\log n)$

#include<bits/stdc++.h>
using namespace std;
struct node
{int x,id;
}c[200005];
int n,m,tmp;
bool cmp(node a,node b)
{return a.x+a.id<=b.x+b.id;//跟思路一样排序
}
int main()
{int t;cin>>t;while(t--){memset(c,0,sizeof(c));cin>>n>>m;for(int i=1;i<=n;i++){cin>>tmp;c[i].x=tmp;c[i].id=i;}sort(c+1,c+n+1,cmp);int i=0;while(m>=0&&i<=n){i++;m=m-c[i].x-c[i].id;}cout<<i-1<<endl;	}return 0;
}

Teleporters (Hard Version)

思路：这一题就是先前缀和记录一下能用的传送门的价值之和，然后在使用二分答案，但是因为起点是 $0$ 的缘故，所以还要另外枚举 $0$ 点。

#include<bits/stdc++.h>
#define maxn 2900001
#define int long long
using namespace std;
int T,n,m,ans,a[maxn],s[maxn];
int check(int c,int x,int id)
{//二分最长的合法前缀区间int l=1,r=n,sum=-1;while(l<=r){int mid=l+r>>1;if(s[mid]-(mid>=id?x:0)<=c)sum=mid+(mid>=id?-1:0),l=mid+1;//特判x的影响else r=mid-1;}return sum==-1?0:sum;//可能无解
}
signed main()
{scanf("%lld",&T);while(T--){ans=0;map<int,int>mp;//记录位置scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);s[i]=min(a[i]+(n-i+1),a[i]+i);//取最小花费}sort(s+1,s+n+1);for(int i=1;i<=n;i++) mp[s[i]]=i,s[i]+=s[i-1];//前缀和for(int i=1;i<=n;i++){if(m-a[i]-i<0) continue;//可能不合法ans=max(ans,check(m-a[i]-i,min(a[i]+(n-i+1),a[i]+i),mp[min(a[i]+(n-i+1),a[i]+i)])+1);//注意要加上当前点i}printf("%lld\n",ans);}return 0;
}

国王游戏

思路:就是按照$a_i{b}_i$​​的大小从小到大排序

证明：我们不妨设两个人分别写了 $a_1,b_1,a_2,b_2$ 且满足 $a_1{b}_1>a_2{b}_2$ 则有 $\frac{a_2}{b_1}=\frac{a_1}{b_2}$​

所以有一下两种情况

1. 1在2的前面
2. 1在2的后面

设在设在 $1,2$ 之前所有人左手乘积为 $k$，那么对于第一种情况，我们的答案就是

a n s 1 = max ⁡ ( k b 1 , k a 1 b 2 )