The Dragon of Loowater_uva11292

The Dragon of Loowater_uva11292_poj3646

　　　　排序+贪心

　　　　注意边界的处理。

　　　　我是用龙的头数进行for循环，依次对骑士进行选择。假如符合条件的骑士都用完了，而龙头还没有砍完，则不成功。

　　　　32ms

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int _max=20000+10;
 5 int a[_max];
 6 int b[_max];
 7 int main()
 8 {
 9     int n,m;
10     while(scanf("%d%d",&n,&m)!=EOF){
11         if(n==0&&m==0)
12             break;
13         for(int i=0;i<n;i++)
14             scanf("%d",&a[i]);
15         for(int i=0;i<m;i++)
16             scanf("%d",&b[i]);
17         sort(a,a+n);
18         sort(b,b+m);
19         if(m<n||a[n-1]>b[m-1])
20             printf("Loowater is doomed!
");
21         else{
22             int ans=0;
23             int v=-1;
24             for(int i=0;i<n;i++){
25                 v++;
26                 while(b[v]<a[i]&&v<m){
27                     v++;
28                 }
29                 if(v>=m){
30                     ans=-1;
31                     break;
32                 }
33                 ans+=b[v];
34             }
35             if(ans>=0)
36                 printf("%d
",ans);
37             else
38                 printf("Loowater is doomed!
");
39         }
40     }
41     return 0;
42 }

View Code

　　　　而刘汝佳的训练指南里，是用骑士的人数进行for循环，依次砍掉龙头，要是最后龙头数>=n,则说明砍完了，成功。

　　　　他的代码写的比我漂亮多了。

　　　　47ms

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=20000+5;
 5 int a[maxn];
 6 int b[maxn];
 7 int main()
 8 {
 9     int n,m;
10     while(scanf("%d%d",&n,&m)==2&&n&&m){
11         for(int i=0;i<n;i++)
12             scanf("%d",&a[i]);
13         for(int i=0;i<m;i++)
14             scanf("%d",&b[i]);
15         sort(a,a+n);
16         sort(b,b+m);
17         int cur=0;
18         int cost=0;
19         for(int i=0;i<m;i++){
20             if(b[i]>=a[cur]){
21                 cost+=b[i];
22                 if(++cur==n)
23                     break;
24             }
25         }
26         if(cur<n)
27             printf("Loowater is doomed!
");
28         else
29             printf("%d
",cost);
30     }
31     return 0;
32 }

View Code