贪心入门题解

A-hdu2037

题意：给定若干电视节目的开始和结束时间（整点时刻），试计算出最多能完整看完的节目数。

思路：按照节目结束时间排序，选择结束时间靠前的节目。　　

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node
31 {
32     int s,e;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     return a.e<b.e;
38 }
39 
40 int main()
41 {
42     int n;
43     while(~scanf("%d",&n),n)
44     {
45         for(int i=1;i<=n;++i)    scanf("%d %d",&p[i].s,&p[i].e);
46         sort(p+1,p+1+n,cmp);
47         int ans=0,tmp=-1;
48         for(int i=1;i<=n;++i)
49         {
50             if(p[i].s>=tmp)    ans++,tmp=p[i].e;
51         }
52         printf("%d
",ans);
53     }
54 }

代码

B-hdu1009

题意：已知若干烧烤店的肉的数量和总价，问给定金额的钱最多可以购买多少肉。

思路：计算给定肉的单价，按照单价排序，购买性价比高的。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node
31 {
32     double x,y,a;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     return a.a>b.a;
38 }
39 
40 int main()
41 {
42     int n,m;
43     while(~scanf("%d %d",&m,&n))
44     {
45         if(n==-1&&m==-1)    break;
46         for(int i=1;i<=n;++i)
47         {
48             scanf("%lf %lf",&p[i].x,&p[i].y);
49             p[i].a=p[i].x/p[i].y;
50         }
51         sort(p+1,p+1+n,cmp);
52         double ans=0;
53         for(int i=1;i<=n;++i)
54         {
55             if(m>=p[i].y)    
56             {
57                 m-=p[i].y;
58                 ans+=p[i].x;
59             }
60             else 
61             {
62                 ans+=p[i].a*m;
63                 m=0;
64             }
65         }
66         printf("%.3f
",ans);
67     }
68 }

代码

C-hdu1050

题意：给你400个房间，每个房间标号，一条栈道的一边全是奇数，另一边全是偶数，每十分钟内每个位置的两个房间中间的栈道只能通行1次，问把这n条桌子从不同房间放到另一个房间中至少要几分钟。

思路1：贪心。每次同时移动尽可能多的桌子，需要移动的次数$*10$。

思路2：统计每个位置最多的通行次数，即至少移动的次数。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node
31 {
32     int l,r,flag;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     return a.l<b.l;
38 }
39 
40 int main()
41 {
42     int t;
43     scanf("%d",&t);
44     while(t--)
45     {
46         int n;
47         scanf("%d",&n);
48         for(int i=1;i<=n;++i)
49         {
50             scanf("%d %d",&p[i].l,&p[i].r);
51             p[i].flag=0;
52             p[i].l=(p[i].l+1)/2;
53             p[i].r=(p[i].r+1)/2;
54             if(p[i].l>p[i].r)    swap(p[i].l,p[i].r);
55         }
56         sort(p+1,p+1+n,cmp);
57         int R=-1,ans=0;
58         for(int i=1;i<=n;++i)
59         {
60             if(p[i].flag)    continue;
61             R=p[i].r;
62             p[i].flag=1;
63             ans++;
64             for(int j=i+1;j<=n;++j)
65             {
66                 if(p[j].flag)    continue;
67                 if(p[j].l>R)    
68                 {
69                     R=p[j].r;
70                     p[j].flag=1;
71                 }
72             }
73         }
74         printf("%d
",ans*10);
75     }
76 }

思路1代码

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 int cnt[maxn];
31 
32 int main()
33 {
34     int t;
35     scanf("%d",&t);
36     while(t--)
37     {
38         int n,l,r;
39         scanf("%d",&n);
40         int ans=0;
41         memset(cnt,0,sizeof cnt);
42         for(int i=1;i<=n;++i)
43         {
44             scanf("%d %d",&l,&r);
45             l=(l+1)/2;
46             r=(r+1)/2;
47             if(l>r) swap(l,r);
48             for(int j=l;j<=r;++j) cnt[j]++;
49         }
50         for(int i=0;i<=200;++i)    ans=max(ans,cnt[i]);
51         printf("%d
",ans*10);
52     }
53 }

思路2代码

D-poj1017

题意：一家工厂生产的产品规格分为1×1, 2×2, 3×3, 4×4, 5×5, 6×6，高都是h。工厂要把它们包在6×6×h的包装袋中。工厂想让包装数尽可能少。

思路：优先装规格大的产品。可以试着画图，比如装$3*3$规格的产品的时候，四个四个装，如果有多余的部分分情况讨论。注意细节问题。

 1 //#include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 int a[10];
31 
32 int main()
33 {
34     while(~scanf("%d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6]))
35     {
36         for(int i=1;i<=6;++i)    
37         {
38             if(a[i])    break;
39             if(i==6)    return 0;    
40         }
41         int ans=a[6];
42         if(a[5])
43         {
44             ans+=a[5];
45             a[1]=max(0,a[1]-a[5]*11);
46         }
47         if(a[4])
48         {
49             ans+=a[4];
50             if(a[4]*5>a[2])
51             {
52                 a[1]=max(0,a[1]-(a[4]*5-a[2])*4);
53                 a[2]=0;
54             }
55             else a[2]-=a[4]*5;
56         }
57         if(a[3])
58         {
59             ans+=a[3]/4;
60             a[3]%=4;
61             if(a[3]==1 )
62             {
63                 ans++;
64                 if(a[2]>=5)    a[2]-=5,a[1]=max(0,a[1]-7);
65                 else a[1]=max(0,a[1]-7-(5-a[2])*4),a[2]=0;
66             }
67             else if(a[3]==2)
68             {
69                 ans++;
70                 if(a[2]>=3)    a[2]-=3,a[1]=max(0,a[1]-6);
71                 else a[1]=max(0,a[1]-6-(3-a[2])*4),a[2]=0;
72             }
73             else if(a[3]==3)
74             {
75                 ans++;
76                 if(a[2]>=1)    a[2]-=1,a[1]=max(0,a[1]-5);
77                 else a[1]=max(0,a[1]-9);
78             }
79         }
80         if(a[2])
81         {
82             ans+=a[2]/9;
83             a[2]%=9;
84             if(a[2]) ans++;
85             a[1]=max(0,a[1]-(6*6-a[2]*4));
86         }
87         if(a[1])
88         {
89             ans+=a[1]/36;
90             a[1]%=36;
91             if(a[1])    ans++;
92         }
93         printf("%d
",ans);
94     }
95 }

代码

E-hdu1051

题意：将木棍放在机器里处理，第一根需要一分钟，剩余的如果大于等于前边放入的长度和重量，就不用费时间，否则需要一分钟，求处理完这堆木棍的最短时间。

思路：先按照木棍长度排序，长度一样按照重量排序。因长度有序，只需考虑重量，对于当前的每根木棍，只需判断重量是否大于上一根即可。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node 
31 {
32     int l,w,flag;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     if(a.l==b.l)    return a.w<b.w;
38     return a.l<b.l;
39 }
40 
41 int main()
42 {
43     int t;
44     scanf("%d",&t);
45     while(t--)
46     {
47         int n;
48         scanf("%d",&n);
49         for(int i=1;i<=n;++i)
50         {
51             scanf("%d %d",&p[i].l,&p[i].w);
52             p[i].flag=0;
53         }
54         sort(p+1,p+1+n,cmp);
55         int ans=0,tmp;
56         for(int i=1;i<=n;++i)
57         {
58             if(p[i].flag)    continue;
59             ans++;
60             p[i].flag=1;
61             tmp=p[i].w;
62             for(int j=i+1;j<=n;++j)
63             {
64                 if(p[j].flag)    continue;
65                 if(p[j].w>=tmp)
66                 {
67                     p[j].flag=1;
68                     tmp=p[j].w;
69                 }
70             }
71         }
72         printf("%d
",ans);
73     }
74 }

代码

F-hdu1338

题意：假定包括你一共有$M$个人在玩一个特殊的卡片游戏，一开始，每个玩家拿$N$张卡片，卡的点数最多是$N*M$。而且卡数是互异的，每一轮中，每个玩家选择一张卡和其它玩家比较，谁的点数最大谁就赢得这一轮．然后开始下一轮，在$N$轮之后，当所有玩家的卡片都选过之后，赢得轮数最多的玩家获胜．给你一开始的卡片，说出你至少赢得多少轮。

思路：问的至少所以要考虑最坏的情况。以为只要对手中有一个人的牌更大，那么就是输。对面的玩家根据手里的牌联合可以算出我的牌，假设对方知道我的出牌顺序，那么这是最坏的情况。假设我是从大到小出牌，如果对面有比我大的牌，只需要出一张最大的牌以及$M-2$张最小的牌，这是在保证对手赢的最优出牌方式。如果对面发现没有比我还要大的牌，那么这局我必赢，所以对面会全部出最小的牌。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 int a[maxn];
31 int vis[maxn];
32 queue<int>q;
33 
34 bool cmp(const int &a,const int &b)
35 {
36     return a>b;
37 }
38 
39 int main()
40 {
41     int n,m,cas=0;
42     while(~scanf("%d %d",&m,&n),n,m)
43     {
44         while(!q.empty())    q.pop();
45         memset(vis,0,sizeof vis);
46         for(int i=1;i<=n;++i) scanf("%d",&a[i]),vis[a[i]]=1;
47         sort(a+1,a+1+n,cmp);
48         for(int i=n*m;i>=1;--i)
49         {
50             if(vis[i]) continue ;
51             q.push(i);
52         }
53         int ans=0;
54         for(int i=1;i<=n;++i)
55         {
56             int x=q.front();
57             if(a[i]>x) ans++;
58             else q.pop();
59         }
60         printf("Case %d: %d
",++cas,ans);
61     }
62 }

代码

G-hdu1789

题意：有$n$门功课，每门功课有截止时间和未完成需要扣除的分数，没完成一门功课需要花费一天的时间，问最少需要扣除的分数。

思路：因为没门作业需要完成的时间是一样的，所以我们优先做需要扣除分数多的功课，并且在可以完成的时间内越迟完成越好。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node
31 {
32     int val,time;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     return a.val>b.val;
38 }
39 
40 int vis[maxn];
41 
42 int main()
43 {
44     int t;
45     scanf("%d",&t);
46     while(t--)
47     {
48         int n;
49         scanf("%d",&n);
50         memset(vis,0,sizeof(vis));
51         for(int i=1;i<=n;++i)    scanf("%d",&p[i].time);
52         for(int i=1;i<=n;++i)    scanf("%d",&p[i].val);
53         sort(p+1,p+1+n,cmp);
54         int ans=0;
55         for(int i=1;i<=n;++i)
56         {
57             ans+=p[i].val;
58             for(int j=p[i].time;j>=1;--j)
59             {
60                 if(vis[j])    continue;
61                 vis[j]=1;
62                 ans-=p[i].val;
63                 break;
64             }
65         }
66         printf("%d
",ans);
67     }
68 }

代码

H-poj1700

题意：只有一艘船，能乘$2$人，船的运行速度为$2$人中较慢一人的速度，过去后还需一个人把船划回来，问把$n$个人运到对岸，最少需要多久。

思路：首先按照速度排序。考虑单独把最慢的两个人运到河对岸的最快方案。

　　　　1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来。

　　　 2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来。

　　　　两种方案需要的时间分别为： 1. $t[2] + t[1] + t[n] + t[2] = t[1] + 2 * t[2] + t[n]$

　　　　　　　　　　　　　　　　　 2. $t[n] + t[1] + t[n-1]+t[1] = 2 * t[1] +t[n-1] + t[n]$

 1 //#include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 int a[maxn];
31 
32 int main()
33 {
34     int t;
35     scanf("%d",&t);
36     while(t--)
37     {
38         int n;
39         scanf("%d",&n);
40         for(int i=1;i<=n;++i)
41         {
42             scanf("%d",&a[i]);
43         }
44         sort(a+1,a+1+n);
45         int ans=0;
46         while(n>=4)
47         {
48             ans+=min(a[1]*2+a[n-1]+a[n],a[1]+a[2]*2+a[n]);
49             n-=2;
50         }
51         if(n==3) ans+=a[3]+a[1]+a[2];
52         if(n==2) ans+=a[2];
53         if(n==1) ans+=a[1];
54         printf("%d
",ans);
55     }
56 }

代码

I-poj1328

题意：一个二维坐标系的一二象限代表海，三四象限代表陆地，$x$轴代表海岸线，海里有一些岛屿，海岸线上准备装一些雷达，每个雷达的作用范围是一个半径为$d$的圆，问覆盖全部岛屿最少需要装多少个雷达。

思路：根据岛屿的位置，我们可以计算出海岸线上需要装雷达的范围。可以用 $[ l , r ]$ 区间的线段表示。那么我们的问题就转换为至少需要多少个点可以覆盖这些线段。把线段先按照 $l$ 排序，再按照 $r$ 排序。判断线段的关系：如果两个区间相交，无需操作；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。

 1 //#include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e14+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node
31 {
32     double l,r;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     if(a.l==b.l)    return a.r<b.r;
38     return a.l<b.l;
39 }
40 
41 int main()
42 {
43     int n,d;
44     int cas=0;
45     while(~scanf("%d %d",&n,&d),n,d)
46     {
47         int flag=0;
48         for(int i=1;i<=n;++i)
49         {
50             int x,y;
51             scanf("%d %d",&x,&y);
52             if(y>d)    flag=1;
53             else
54             {
55                 double s=sqrt(d*d-y*y);
56                 p[i].l=x-s;
57                 p[i].r=x+s;
58             }
59         }
60         if(flag)    printf("Case %d: -1
",++cas);
61         else 
62         {
63             sort(p+1,p+1+n,cmp);
64             double R=p[1].r;
65             int ans=1;
66             for(int i=2;i<=n;++i)
67             {
68                 if(p[i].l<=R && p[i].r>=R)    continue;
69                 else if(p[i].l<=R && p[i].r<R) R=p[i].r;
70                 else ans++,R=p[i].r;
71             }
72             printf("Case %d: %d
",++cas,ans);
73         }
74     }
75 }

代码

J-hdu6709

题意：有$n$条鱼，煮每条鱼需要$t[i]$的时间，钓每条鱼需要$k$的时间。每次你可以选择花费$k$的时间钓一条鱼或者把鱼从锅里取出来放进去另一条鱼。在钓鱼的途中不能换鱼，一条鱼可以煮超过$t$的时间，问最少需要多少时间可以把所有的鱼钓上来并且煮熟。

思路：第一条鱼必须要钓，花费$k$的时间，然后对于每条在煮的鱼的前$k$倍数的时间用来钓鱼，余下的那段不足$k$的时间，我们可以有$2$种操作：

1.等这条鱼煮完，然后换上新的鱼。

2.去调新的鱼，让这条鱼再煮$k$的时间。

　　　很显然，如果在煮别的鱼的间隙能把$n$条鱼都钓上来，那么显然不需要花费另外的时间再去钓鱼，只用等这条鱼煮完，换上新的鱼。如果在煮鱼间隙无法钓完$n$条鱼，那么必须再花费$k$的时间去钓鱼。在这多花费的$k$的时间无法全部利用来煮鱼，但是我们希望浪费的时间越少越好。什么是浪费的时间呢？本来一条鱼需要煮$t$$(t<k)$的时间，但是现在需要$k$的时间，那么$k-t$的时间就是浪费的时间，我们希望这个时间越小越好，那么$t$尽可能大。

　　我们整理一下，如果煮鱼间隙可以钓$x$条鱼，那么另外$y=n-x$条鱼需要单独花费$k$的时间钓，把煮鱼时间$%k$后从小到大排序，那么后$y$条鱼$(x-n)$采取方案$2$，前$x$条鱼采取方案$1$。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e18+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 ll a[maxn];
31 
32 int main()
33 {
34     int T;
35     scanf("%d",&T);
36     while(T--)
37     {
38         int n;
39         ll k,ans;
40         scanf("%d %lld",&n,&k);
41         ans=k;
42         for(int i=1;i<=n;++i)  
43         {
44             scanf("%lld",&a[i]);
45             ans+=a[i]/k*k;
46             a[i]%=k;
47         } 
48         sort(a+1,a+1+n);
49         ll x=ans/k; //表示在煮鱼期间可以钓到的鱼的数量；
50         if(x>n) x=n;
51         if(x<n) ans+=(n-x)*k;//每条鱼需要另外花费k的时间去钓；
52         for(int i=x;i>=1;--i)//x-n标号的捕鱼时间可以用来煮鱼，1-x标号的鱼的煮鱼时间无法省略。 
53         {
54             ans+=a[i];
55         }
56         printf("%lld
",ans);
57     }
58 }

代码

K-poj2054

题意：给定一棵树，每个节点有一个权值，现要求给这些节点进行排列，设排列后的节点顺序为$v_1-v_n$，它们的权值是$val_1-val_n$，那么我们要求一种排列使得$val_1*1+val_2*2+...+val_n*n$最小。还有一个限制就是这个排列满足每个节点的父节点都排在该结点之前。

思路：如果没有限制父节点必须在子节点前面，那么这道题非常的简单，只要按照$val$排个序。对于现在这个问题，我们考虑，对于一个$val$最大的点，我门尽可能希望它排的越前面。那么，最优的方案就是紧贴着它的父亲节点。因为它们的位置确定了，我们可以把它们合并成一个点。那么对于两个点堆，我们怎样排它们的位置，使得答案最优呢？我画了一个极其丑陋的图，大家可以勉强看一下。

由图片可以看出，点堆的平均值越大，排越前，越优。所以，我们每次找出一个平均值最大的点堆，把它们和父亲点（堆）合并。那怎么计算答案呢？累加计算即可。因为，比如一个点$p$在点$A$中位于第$i$的位置，点$A$在点$B$中位于第$j$的位置。那么点$p$在点堆$B$中位于第$i+j$的位置。根据分配律，若$ans=p*(i+j)=p*i+p*j$，所以每次合并点堆的时候更新答案就好了。

 1 //#include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e18+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 int fa[maxn],cnt[maxn];
31 int val[maxn];
32 
33 int main()
34 {
35     int n,rt;
36     while(~scanf("%d %d",&n,&rt),n,rt)
37     {
38         for(int i=1;i<=n;++i)
39         {
40             scanf("%d",&val[i]);
41             cnt[i]=1;
42         }
43         for(int i=1;i<n;++i)
44         {
45             int x,y;
46             scanf("%d %d",&x,&y);
47             fa[y]=x;
48         }
49         int ans=0;
50         for(int k=1;k<n;++k)
51         {
52             double maxx=0;
53             int node;
54             for(int i=1;i<=n;++i)
55             {
56                 if(i!=rt && val[i]*1.0/cnt[i]>maxx)
57                 {
58                     maxx=1.0*val[i]/cnt[i];
59                     node=i;
60                 }
61             }
62             for(int i=1;i<=n;++i)
63             {
64                 if(fa[i]==node) fa[i]=fa[node];
65             }
66             ans+=cnt[fa[node]]*val[node];
67             cnt[fa[node]]+=cnt[node];
68             val[fa[node]]+=val[node];
69             val[node]=0;
70         }
71         ans+=val[rt];
72         printf("%d
",ans);
73     }
74 }

代码

L-zoj2883

题意：商店折扣每三件可以免一件，已知所有商品的价格，求最大优惠金额。

思路：金额排序，从大到小每三个取三个中小的那个作为优惠。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e18+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 int a[maxn];
31 
32 int main()
33 {
34     int t;
35     scanf("%d",&t);
36     while(t--)
37     {
38         int n;
39         scanf("%d",&n);
40         for(int i=1;i<=n;++i)
41         {
42             scanf("%d",&a[i]);
43         }
44         sort(a+1,a+1+n);
45         int cnt=0;
46         int ans=0;
47         for(int i=n;i>=1;--i)
48         {
49             cnt++;
50             if(cnt==3)
51             {
52                 cnt=0;
53                 ans+=a[i];
54             }
55         }
56         printf("%d
",ans);
57     }
58 }

代码

M-hdu3979

题意：一个游侠和多个怪兽决斗，怎么样击杀怪兽会使游侠的耗血最少。怪兽不会一个一个的跟你打，他们也不傻，他们对你群殴，怪兽血量为$HＰ$，攻击力为$Ｓ$，游侠每秒的攻击力为$ｍ$。

思路：对于两个怪兽$A$和$B$,血量分别为$Ha$和$Hb$，攻击力分别为$a$和$b$。那么我们有两种攻击方法：

　　　　1.先攻击$A$再攻击$B$。耗血量为：$Ha/m*(a+b)+Hb/m*b$。

　　　　2.先攻击$B$再攻击$A$。耗血量为：$Hb/m*(a+b)+Ha/m*a$。

　　　　比较两种的耗血量其实化简一下就是比较$Ha/m*b$和$Hb/m*a$的大小。排序即可。

 1 #include<bits/stdc++.h>
 2 #include <set>
 3 #include <map>
 4 #include <stack>
 5 #include <cmath>
 6 #include <queue>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 
14 #define ll long long
15 #define PLL pair<ll,ll>
16 #define PII pair<int,int>
17 #define bug printf("*********
")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls root<<1
22 #define rs root<<1|1
23 
24 using namespace std;
25 const int inf=0x3f3f3f3f;
26 const ll Inf=1e18+7;
27 const int maxn=1e5+5;
28 const int mod=1e9+7;
29 
30 struct node 
31 {
32     int hp,g;
33 }p[maxn];
34 
35 bool cmp(const node &a,const node &b)
36 {
37     return a.hp*b.g<b.hp*a.g;
38 }
39 
40 int main()
41 {
42     int t;
43     scanf("%d",&t);
44     for(int cas=1;cas<=t;++cas)
45     {
46         int n,m;
47         ll sum=0;
48         scanf("%d %d",&n,&m);
49         for(int i=1;i<=n;++i)
50         {
51             scanf("%d %d",&p[i].hp,&p[i].g);
52             p[i].hp=ceil((double)p[i].hp/(double)m);
53             sum+=p[i].g;
54         }
55         sort(p+1,p+1+n,cmp);
56         ll ans=0;
57         for(int i=1;i<=n;++i)
58         {
59             ans+=sum*p[i].hp;
60             sum-=p[i].g;
61         }
62         printf("Case #%d: %lld
",cas,ans);
63     }
64 }

代码