箭無虛發

Time Limit: 1000 MS	Memory Limit: 65536 KB
Total Submissions: 128	Accepted: 21

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!
題解：這道題在做的時候就用到一些技巧了，其實成績良在此題內屬于多余條件，得優的時間>得中的時間。 所以一開始全部得中，得到最小花費的時間，如果此時間都大于考核的時間，那么必定會得差 然后用貪心法依次往里加一個優試試，如果滿足則加入，所以會按得優的時間減去得中的時間a.a-a.c排序，這樣保證每次添加進去最小的時間，直到結束或超過考核時間 最后就會得出答案了
#include <iostream> #include <cstdio> #include <algorithm>using namespace std;struct J {int a, b, c; }a[1002];bool cmp(J a, J b) {return a.a - a.c < b.a - b.c; }int main(int argc, char const *argv[]) {int T, n, t, s;scanf("%d", &T);while (T--){s = 0;scanf("%d", &n);for (int i=0; i<n; i++) {scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);s += a[i].c;}scanf("%d", &t); //如果全得“中”的時間（最小花費）>考核時間，就不能做到箭無虛發if (s > t) printf("Oh,my god!\n");else {sort(a, a+n, cmp);//排序用到技巧，（得優的時間-得中的時間）按升序排序int cnt = 0;for (int i=0; i<n; i++) {if (s - a[i].c + a[i].a <= t) {s = s - a[i].c + a[i].a;//加一個優并減去一個中的時間，貪心策略cnt++;}else break;}printf("%d\n", cnt);}}return 0; }

總結

以上是生活随笔為你收集整理的安徽省2016“京胜杯”程序设计大赛_C_箭无虚发的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。