贪心算法（提高篇）weixin46434074的博客-

这次学习贪心算法，我看到了一个很好玩的例子，我在另一篇博客里写过一遍了，但是这篇博客还想再写一下
在一个n*m的方格阵中，每一格子赋予一个值（权值），规定每次移动只能向上或者向右。现试找一条路径，使其从左下角至右上角所经过的权值之和最大。

这个题用贪心的方法求解时路径为1->3->4->6
用DP求解则是1->2->10->6
这个题就不适合用贪心算法求解，用贪心的方法解出来得到的并不是最优解，所以在解题时判断贪心是否适用就显得十分重要了。
1422：【例题1】活动安排
【题目描述】
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。选择出由相互兼容的活动组成的最大集合。

【输入】
第1行一个整数n(n≤1000)，接下来n行，每行两个整数si和fi。

【输出】
输出尽可能多的互相兼容的活动个数。

【输入样例】
4
1 3
4 6
2 5
1 7
【输出样例】
2

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string>  using namespace std; int n,ans=1,t; struct app { int s,e; }a[1005];  bool cmp(app x,app y) { return x.e <y.e ; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].s ,&a[i].e ); sort(a+1,a+n+1,cmp);          t=a[1].e ; for(int i=2;i<=n;i++) { if(a[i].s >=t) {             ans++;             t=a[i].e ; } } printf("%d",ans); return 0; } 

1423：【例题2】种树
【题目描述】
现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成1…N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量较少政府的支出。

【输入】
第一行包含数据N，M，区域的个数(0<N≤30000)，房子的数目(0<m≤5000)；

下面的m行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

【输出】
输出一个数，为满足所有居民的要求，所需要种树的最少数量。

【输入样例】
9 4
3 5 2
1 4 2
4 6 2
8 9 2
【输出样例】
5

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string>  using namespace std; int n,m,ans=0,t,k=0; bool vis[50000]; struct app { int s,e,v; }a[5005];  bool cmp(app x,app y) { return x.e <y.e ; } int main() { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].s ,&a[i].e ,&a[i].v ); sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++) {         k=0; for(int j=a[i].s ;j<=a[i].e ;j++) if(vis[j]) k++; if(k>=a[i].v ) continue; else { for(int z=a[i].e ;z>=a[i].s;z--) { if(!vis[z]) {                     k++;                       ans++;                     vis[z]=1; if(k>=a[i].v ) break; } } } } printf("%d",ans); return 0; } 

1424：【例题3】喷水装置
【题目描述】
长 L 米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

【输入】
输入包含若干组测试数据。

第一行一个整数 T 表示数据组数；

每组数据的第一行是整数 n、L 和 W；

接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。

【输出】
对每组测试数据输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出 −1 。

【输入样例】
3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
【输出样例】
6
2
-1
【提示】
数据范围：

对于 100% 的数据，n≤15000。

#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; int n,cnt,L,h,x,r; struct SEG{ double x,y; }a[20005]; bool cmp(const SEG &x,const SEG &y){ return x.x<y.x; } void Read(){     cin>>n>>L>>h;     cnt=0; for(int i=1;i<=n;i++){         cin>>x>>r; if(r<=h/2) continue;         cnt++;         a[cnt].x=x-sqrt(r*r-h*h/4.0);         a[cnt].y=x+sqrt(r*r-h*h/4.0); } } void solve(){ double t=0; int ans=0,bj=1,i=1; while(t<L){                           ans++; double s=t; for(;a[i].x<=s&&i<=cnt;i++) if(t<a[i].y) t=a[i].y; if(t==s&&s<L){             cout<<-1<<endl;             bj=0; break; } } if(bj) cout<<ans<<endl; } int main(){ int T;     cin>>T; while(T--){ Read(); sort(a+1,a+1+cnt,cmp); solve(); } return 0; }