集训手册贪心题练习题

HDU1009：

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 #define N 1005
 6 
 7 struct Room{
 8     int j,f;
 9     bool operator<(const Room &m)const{
10         double rate1 = j*1.0/f;
11         double rate2 = m.j*1.0/m.f;
12         return rate1>rate2;
13     }
14 }room[N];
15 
16 int main()
17 {
18     int n,m;
19     while(~scanf("%d%d",&n,&m)){
20         if(n==-1&&m==-1)
21             break;
22 
23         for(int i=0;i<m;i++){
24             scanf("%d%d",&room[i].j,&room[i].f);
25         }
26         sort(room+0,room+m);
27 
28         double ans = 0;
29         for(int i=0;i<m;i++){
30             if(n>room[i].f)
31             {
32                 ans+=room[i].j;
33                 n-=room[i].f;
34             }
35             else{
36                 ans+= n*1.0/room[i].f * room[i].j;
37                 break;
38             }
39         }
40         printf("%.3f
",ans);
41     }
42     return 0;
43 }

HUD 1050

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAX 201
 6 int f(int n){
 7     return (n+1)/2;
 8 }
 9 int a[MAX];
10 int main(){
11     int m,n,x,i,j,t,maxm,times,g;
12     cin>>times;
13     for(g=0;g<times;g++){
14         cin>>x;
15         for(i=0;i<x;i++){
16             cin>>m>>n;
17             if(m>n){
18                 t=m;m=n;n=t;
19             }
20             for(j=f(m);j<=f(n);j++) a[j]++;
21         }
22         maxm=0;
23         for(i=1;i<MAX;i++){
24             if(a[i]>maxm) maxm=a[i];
25         }
26         cout<<10*maxm<<endl;
27         memset(a,0,sizeof(a));
28     }
29     return 0;
30 }

HDU 1587
这道题貌似水的过头了、、、每种花数量足够，那么只要找最小值，只买那么一种类型的花就行了，排序都是浪费

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 int price[1000005];
 5 
 6 int main()
 7 {
 8     int n,m;
 9     while(~scanf("%d%d",&n,&m)){
10         for(int i=0;i<n;i++)
11             scanf("%d",price+i);
12 
13         std::sort(price,price+n);
14 
15         int ans = m/price[0];
16 
17         printf("%d
",ans);
18     }
19 }

HDU 1445

题目大意:

有一个人从宿舍到学校骑自行车的方式很奇怪，必须跟着别人出发，且路上碰到速度快的同学就跟在他后面，给出其他学生的速度和出发时间，计算到达学校的时间。

因为时间计算得到是double值，这里要求ceil向上取整

这题目一开始看没什么思路，现在想想就跟原来很多题目一样，明明很简单，只是自己不会将其的题意转化导致自己做不出。

对于那些出发时间为负数的人来说，我们是根本不用考虑的，因为他们提前出发，他们到达的时间要么就是这个人达不到的，如果能追上，说明这人跟着的同学速度更快，就没必要跟着这个提前出发的了。

而对于那些出发时间为正的来说，因为这个人出发的时间是最早的，所以无论谁先到达都必将经过他，所以他肯定会跟着那个最快的同时到达学校，这么一想，题目就简单了。

记录所有后出发的自行车，找到那个最早到达学校的时间，就是我们要的答案。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 #define N 10005
 5 
 6 double time[N];
 7 
 8 int main()
 9 {
10     int n,v,t;
11     while(~scanf("%d",&n)){
12         if(n==0)
13             break;
14 
15         int k=0;
16         for(int i=0;i<n;i++)
17         {
18             scanf("%d%d",&v,&t);
19             if(t>=0){
20                 time[k++] = (ceil)(4500*1.0/(v*1.0/3.6)+t);
21             }
22         }
23 
24         std::sort(time,time+k);
25 
26         int ans =time[0];
27 
28         printf("%d
",ans);
29     }
30 }

HDU 2570

浓度排序，贪心往下直到不能取为止

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 #define N 105
 5 
 6 double consistence[N];
 7 
 8 int main()
 9 {
10     int n,v,w,con;
11     int T;
12     scanf("%d",&T);
13     while(T--){
14         scanf("%d%d%d",&n,&v,&w);
15 
16         for(int i=0;i<n;i++)
17         {
18             scanf("%lf",&consistence[i]);
19             //consistence[i] = con*1.0/100;
20         }
21 
22         std::sort(consistence,consistence+n);
23 
24         double con1 = 0;
25         int ans =0;
26 
27         for(int i=0;i<n;i++){
28             double tmp = (consistence[i] * v + ans * con1)*1.0 / (ans+v);
29             //printf("%.2f %d %d %.2f %.2f
",consistence[i],v,v1,con,tmp);
30             if(tmp<= w){
31                 ans+=v;
32                 con1 = tmp;
33             }
34             else
35                 break;
36         }
37         printf("%d %.2f
",ans,con1/100);
38     }
39     return 0;
40 }