题目

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
1

Sample 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;
}