office做网站的软件/360营销

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

51nod 1428 活动安排问题

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428

有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
分析：模型图——

我写的笨拙的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
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<b.s;
}
int main()
{//freopen("cin.txt","r",stdin);int n;while(cin>>n){int start=0,sum=0,ans=0;for(int i=0;i<n;i++) {scanf("%d%d",&f[i].s,&f[i].e);f[i].tag=0;}sort(f,f+n,cmp);while(sum<n){while(f[start].tag) start++;int temp=start;sum++;ans++;f[start].tag=1;for(int i=start+1;i<n;i++){if(f[i].tag==0&&f[i].s>=f[temp].e){temp=i;sum++;f[i].tag=1;}}}printf("%d\n",ans);}return 0;
}

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

#include <stdio.h>
#include <algorithm>#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 独木舟

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1432

n个人，已知每个人体重。独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？

分析：贪心题目，思路：船载最重的人和最轻的人的组合。开始用二分写的，但是总有3个测试用例过不了，郁闷~

#include <cstdio>
#include <iostream>
#include <algorithm>
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<n;i++){scanf("%d",&f[i]);}sort(f,f+n,cmp);int k=0,ans=0;while(k<n){if(f[k]+f[n-1]<=m) n--;  //最大值带最小值ans++;k++;}printf("%d\n",ans);}return 0;
}

hdu 5037 Frog

http://acm.hdu.edu.cn/showproblem.php?pid=5037

大意：给出n,m,l，青蛙要从0跳到m，之间还有n个点（石子）存在，青蛙的最远能跳l。上帝可以在任意点任意位置放置任意的石子，帮助青蛙跳跃（诱使其跳的次数尽可能多），问青蛙至少需要跳多少次？

分析：对于一系列的点，有各种跳跃的情况，单纯 的考虑间隔大于L的两点间的情况，为了使得青蛙的跳跃次数最大，有这样的贪心思路

#include <iostream>
#include <algorithm>
#include <cstdio>
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;i<n;i++) scanf("%d",&a[i]);a[n]=m;sort(a,a+n+1);int len1=l,len2,ans=0,cur=0; //开始len1=Lfor(int i=0;i<n+1;i++){len2=a[i]-cur;if(len2==0) continue; //重合的点if(len1+len2<=l){cur=a[i];len1=len1+len2;}else if(len2<=l){ans++;cur=a[i];len1=len2;}else if(len2>l){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;
}