题目
Description
JH苦练10年,终于成为了一个神箭手,在下山之前,大师兄YZ不放心,想考验他,只给他一定时间t,同时给他n支箭,最终根据他的表现,考虑他是否能下山。
对于每发一次箭,YZ给他4种成绩(优、良、中、差),JH有三种拉弓以及瞄准时间a ,b,c(a>=b>=c)分别能拿优,良,中等级,如果不拉弓不瞄(直接射),只能拿差(不能中靶)了。
现在JH想知道,在保证自己弹无虚发(不获得差)的情况下,最多能拿多少个优。
如果JH不能做到弹无虚发,输出Oh,my god!Input
输入数据包含T组:
对于每组数据,第一行为一个整数n,表示总共有n支箭。
(0<n<=1000)
之后n行,每行包含三个数字a,b,c,分别表示拿对应等级所需要花的时间。
(0<c<=b<=a<=1000)
之后一个数字t,表示JH有考核总时间为t
(0<=t<=1e6)Output
对于每组输入,如果JH能箭无虚发,则输出一个数字x,表示最多能拿到的优的数量。如果不能,则输出Oh,my god!
Sample Input
3
1
3 2 1
1
2
3 2 1
3 2 1
4
2
3 2 1
3 2 1
1Sample Output
0
1
Oh,my god!
题解
这道题不是DFS、不是状态压缩BFS,只是一道贪心算法!!
由于优、良、中、差。
更高的等级花费的时间一定大于等于比它低的等级,所以我们只需要记录 优 和 中 的时间
如果全部都是 中 都不能射完所有箭,那么肯定无法完成。应该输出"Oh,my god!\n"
然后我们假设全部射出 优 评分,那么如果时间不够,我们应该将一个评价 优 变成评价 中
为了保证最多的 优 ,我们需要尽可能在一次变换中多省出时间
也即 将 优 和 中 时间差最大的那支箭替换掉
按照这个思路,读入后排序下即可。
代码
/* By:OhYee Github:OhYee HomePage:http://www.oyohyee.com Email:oyohyee@oyohyee.com Blog:http://www.cnblogs.com/ohyee/ かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <set> #include <queue> #include <stack> #include <map> using namespace std; //DEBUG MODE #define debug 0 //循环 #define REP(n) for(int o=0;o<n;o++) const int maxn = 1005; struct Time { int PTime,MTime; int delta; Time(int x=0,int y=0) { PTime = x; MTime = y; delta = x - y; } bool operator < (const Time &rhs)const { return delta > rhs.delta; } }; Time UseTime[maxn]; void Do() { int t,n,UT=0; scanf("%d",&n); int sum = 0; REP(n) { int a,c; scanf("%d%*d%d",&a,&c); sum += c; UT += a; UseTime[o] = Time(a,c); } scanf("%d",&t); if(sum > t) { printf("Oh,my god!\n"); return; } sort(UseTime,UseTime + n); int ans = n; for(int i = 0;UT > t;i++) { ans--; UT -= UseTime[i].delta; } printf("%d\n",ans); } int main() { int T; scanf("%d",&T); while(T--) Do(); return 0; }