高级算法--贪心

下面是对信息学奥赛一本通网站评测上的AC代码的总结

·例一:

题目描述:

  设有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 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int st;
10     int ed;
11 }a[1005];
12 
13 bool cmp(node x,node y)
14 {
15     return x.ed<y.ed;
16 }
17 
18 int main()
19 {
20     int n;
21     scanf("%d",&n);
22     for(int i=1;i<=n;++i)    scanf("%d%d",&a[i].st,&a[i].ed);
23     sort(a+1,a+n+1,cmp);
24     int t=a[1].ed;
25     int ans=1;
26     for(int i=2;i<=n;++i)
27     {
28         if(a[i].st>=t)
29         {
30             ans++;
31             t=a[i].ed;
32         }
33     }
34     printf("%d",ans);
35     return 0;
36 }

 

·例二:

题目描述:

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

代码实现:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 struct line{int s,e,v;}a[5005];
 8 
 9 int n,m;
10 
11 bool used[30005]={0};
12 
13 bool cmp(const line &x,const line &y){return x.e<y.e;}
14 
15 void init()
16 {
17     int i;
18     scanf("%d%d",&n,&m);
19     for(i=1;i<=m;++i) scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].v);
20     sort(a+1,a+m+1,cmp);
21 }
22 
23 void solve()
24 {
25     int i,j,k,ans=0;
26     for(int i=1;i<=m;++i)
27     {
28         k=0;
29         for(j=a[i].s;j<=a[i].e;++j)    if(used[j]) ++k;
30         if(k>=a[i].v) continue;
31         for(j=a[i].e;j>=a[i].s;--j)
32             if(!used[j])
33             {
34                 used[j]=1;
35                 k++;
36                 ans++;
37                 if(a[i].v==k) break;
38             }
39     }
40     printf("%d",ans);
41 }
42 
43 int main()
44 {
45     init();
46     solve();
47     return 0;
48 }

·例三:

题目描述:

长L米,宽W米的草坪里装有n个浇灌喷头。每个喷头都装在草坪中心线上(离两边各W/2米)。我们知道每个喷头的位置(离草坪中心线左端的距离),以及它能覆盖到的浇灌范围。

高级算法--贪心

请问:如果要同时浇灌整块草坪,最少需要打开多少个喷头?

代码实现:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 #define N 300005
 6  
 7 using namespace std;
 8  
 9 const double Eps = 1e-5 ;
10  
11 inline int wread(){
12     char c=getchar ();int flag=1,wans=0;
13     while (c<'0'||c>'9'){if (c=='-') flag=-1;c=getchar ();}
14     while (c>='0'&&c<='9'){wans=wans*10+c-'0';c=getchar ();}
15     return wans*=flag;
16 }
17  
18 int T;
19 int n,L,W;
20 struct node {double lx,rx;int pos,r;}a[N];
21 bool e666 (node x,node y){return x.lx<y.lx;}
22  
23 int main (){
24     T=wread();
25     while (T--){
26         memset (a,0,sizeof a);
27         n=wread();L=wread();W=wread();
28         for (int i=1;i<=n;++i){
29             a[i].pos=wread(),a[i].r=wread();
30             if (a[i].r*a[i].r-(W*1.0/2.0)*(W*1.0/2.0)<0)    a[i].pos=-1,a[i].lx=-1,a[i].rx=-1;
31             //对于不能覆盖完草坪上端的一个圆(例如样例1中的那个夹在草坪中间的圆) 肯定是不会选它的 
32             else {
33                 a[i].lx=max (0.000000,(double)a[i].pos-sqrt((double)a[i].r*(double)a[i].r-(W*1.0/2.0)*(W*1.0/2.0)));
34                 a[i].rx=a[i].pos+sqrt((double)a[i].r*(double)a[i].r-(W*1.0/2.0)*(W*1.0/2.0));                    
35             }
36         }
37  
38         sort (a+1,a+n+1,e666);    
39         
40         int nx=1; 
41         double s=0;//起点 
42         bool F=true;//判断是否能覆盖完整个区间 
43         int ans=0;//记录 
44         
45         while (nx<=n){
46             ans++;
47             double re=s;
48             while (a[nx].lx<=re && nx<=n){//模板 
49                 if (a[nx].rx>=re)    s=max(s,a[nx].rx);
50                 nx++;
51             }
52             if (s>=L)    {break;}
53             if (re==s)    {F=false;break;}//未更新,请画图____即当前区间与下个区间之间 一定有一段距离,不符合全部覆盖的要求,退出 
54         }
55         if (!F)    puts("0");
56         else    printf("%d\n",ans);
57     }
58     return 0;
59 }

·例四:

题目描述:

  某工厂收到了n个产品的订单,这n个产品分别在 A、B 两个车间加工,并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品i在 A,B 两车间加工的时间分别为Ai,Bi。怎样安排这个产品的加工顺序,才能使总的加工时间最短。

这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在 A,B 两车间加工完毕的时间。

代码实现:

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int ans[1005],n,k,i,j,t,a[1005];
 7 int b[1005],m[1005],s[1005];
 8 
 9 void read()
10 {
11     int i;
12     scanf("%d",&n);
13     for(i=1;i<=n;++i) scanf("%d",&a[i]);
14     for(i=1;i<=n;++i) scanf("%d",&b[i]);
15 }
16 
17 void solve()
18 {
19     for(i=1;i<=n;++i){m[i]=min(a[i],b[i]);s[i]=i;}
20     for(i=1;i<=n-1;++i)
21         for(j=i+1;j<=n;++j)
22             if(m[i]>m[j]){swap(m[i],m[j]);swap(s[i],s[j]);}
23     k=0;t=n+1;
24     for(i=1;i<=n;++i)
25         if(m[i]==a[s[i]]){k++;ans[k]=s[i];}
26         else{t--;ans[t]=s[i];}
27     k=0;t=0;
28     for(i=1;i<=n;++i)
29     {
30         k+=a[ans[i]];
31         if(t<k) t=k;
32         t+=b[ans[i]];
33     }
34     printf("%d\n",t);
35     for(i=1;i<=n;++i) printf("%d ",ans[i]);
36     printf("\n");
37 }
38 
39 int main()
40 {
41     read();
42     solve();
43     return 0;
44 }

 

上一篇:P1063 能量项链


下一篇:1005: 整数幂