当前位置：首页 > news >正文

国贸商城网站建设建站合肥网络公司seo

news 2025/9/17 15:56:39

国贸商城网站建设,建站合肥网络公司seo,上海做外贸建站的专业公司,农产品电商网站建设的主要工作贪心算法笔记大概内容贪心就是对于一个问题有很多个步骤，我们在每一个步骤中都选取最优的那一个，最后得出答案。就是在一些函数中可行，但是有些比如二次函数，因为它的转折点不一定最优，就是不可行的。那么如何判断贪心呢？有这么几种看时间复杂度，一般的就是 O ( n…

贪心算法笔记

大概内容

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

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

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

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

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

例题讲解

凌乱的yyy / 线段覆盖

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

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

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

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

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

时间复杂度： $\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$ 排序，就好了。

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

时间复杂度： $\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;
}