首页 > 代码库 > Codeforces 230A

Codeforces 230A

2024-07-12 23:03:46   218人阅读

1.题意描述：

Kirito 要打n个怪兽，每个怪兽有两种属性(xi,yi)，xi代表怪兽的力量，yi代表击败怪兽后可以为Kirito自己增加的力量。初始时， Kirito有s力量，只有当Kirito的当前力量s比怪兽的力量xi的时候， Kirito才能击败这只怪兽i，同时，他自己的力量还将增加yi
你可以按任意顺序挑战这些怪兽，问Kirito最终能否击败所有的n只怪兽。

2.解题思路：

贪心算法+排序算法

巨人要打赢所有怪兽必须先打赢力量最小的怪兽，然后汲取力量y后在攻打力量第二大的怪兽，如此往复，直到巨人的力量小于或等于怪兽的力量时就输出no，否则输出yes。

3.代码细节：注意本题中结构体类型变量的排序，自己做题时临时写了一个排序算法（坑爹）。

 1 #include<iostream> 2 #include <algorithm>//头文件不可丢  3 using namespace std; 4 struct dragon 5 { 6     int x,y; 7 }dra[5]; 8 int cmp(dragon a,dragon b){ 9     return a.x < b.x;//return a.x>b.x 10 }//注意cmp函数的书写，它代表按升序排列，稍加修改就可表示按降序排列 11 int main()12 {13     for(int i=0;i<5;i++)14     {15         scanf("%d%d",&dra[i].x,&dra[i].y);16     }17     sort(dra,dra+5,cmp);18     for(int s=0;s<5;s++)19     printf("%d %d\n",dra[s].x,dra[s].y);20     return 0;21 }

4.本题源码：

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 1010; 5 struct Dragon{ 6     int x,y; 7     bool operator < (const Dragon &rhs) const{ 8         return x < rhs.x; 9     }10 }dragon[1010];11 12 int main(){13     int s,n;14     scanf("%d%d",&s,&n);15     for(int i = 0;i < n;i++){16         scanf("%d%d",&dragon[i].x,&dragon[i].y);17     }18     sort(dragon,dragon+n);//默认排序为从小到大19     bool flag = 1;20     for(int i = 0;i < n;i++){21         if(s <= dragon[i].x){22             flag = 0;23             break;24         }else{25             s += dragon[i].y;26         }27     }28     if(flag)    puts("YES");29     else        puts("NO");30     return 0;31 }


联系
我们