贪心一练

贪心一练

很多时候遇到贪心，知道它是贪心想要写好却不是那么容易，现在写下3题，回顾一下那些经典的贪心思维。

51nod 1428 活动安排问题

​​#include #include using namespace std;const int N=1e4+5;struct node{ int s,e,tag;}f[N];int cmp(node a,node b){ return a.s>n){ int start=0,sum=0,ans=0; for(int i=0;i=f[temp].e){ temp=i; sum++; f[i].tag=1; } } } printf("%d\n",ans); } return 0;}

网站上见识到的更好的代码，效率更高：

#include #include #define MAXN 10000int t[MAXN*2];int main() { int n, i, s, f; int ans = 0, tmp = 0; scanf( "%d", &n ); n *= 2; for( i = 0; i < n; i += 2 ) { scanf( "%d%d", &s, &f ); t[i] = s * 2 + 1; t[i+1] = f * 2; } std::sort( t, t + n ); for( i = 0; i < n; ++i ) { if( t[i] & 1 ) { ++tmp; if( tmp > ans ) ans = tmp; } else --tmp; } printf( "%d\n", ans ); return 0;}

51nod 1432 独木舟

​​#include #include using namespace std;int f[10005],n,m;int cmp(int a,int b){ return a>b;}int main(){ //freopen("cin.txt","r",stdin); while(cin>>n>>m){ for(int i=0;i

hdu 5037 Frog

​​的考虑间隔大于L的两点间的情况，为了使得青蛙的跳跃次数最大，有这样的贪心思路

如图所示的方案能使得最小空间花费最多的跳跃次数。

每次研究新的点，增长长度len2必须和已增长度len1相加，他们的和len1+len2与L比较，小于等于自然不需要跳跃，更新len1,和cur (len2=pos[i]-cur)，大于的话则分类讨论：len2<=L，仅仅步数增加，上帝不会出手，大于的话，上帝表演的时间到了：ans+=2*(len2/(L+1)). 设temp=len2%(L+1)+len1. if(temp<=L) 不增加跳跃次数，否则增加跳跃次数。

#include #include #include using namespace std;const int N=2e5+10;int a[N];int main(){ //freopen("cin.txt","r",stdin); int t,ca=1; int n,m,l; cin>>t; while(t--){ scanf("%d%d%d",&n,&m,&l); for(int i=0;il){ ans+=len2/(l+1)*2; int temp=len2%(l+1); if(temp+len1<=l){ len1=temp+len1; cur=a[i]; } else { cur=a[i]; ans++; len1=temp; } } } printf("Case #%d: %d\n",ca++,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。