题目链接 ： C - Petya and Exam
大意：给n道题目，标记好了难度，难题要花b分钟，简单题画a分钟，每道题限制在ti分钟内做完，如果所用的时间超过了ti则记0分。解一题得一分。给你n,T,a,b，每题难度，第i题的ti，求最大得分。
思路：按ti进行从小到大排序，得到新顺序 Ti，预处理出做到Ti对应的题做的情况下还能做几道简单题（加上什么都不做的情况），对新顺序进行遍历，算出做Ti对应的题的时候最大得分，取循环的最大得分即结果。
代码：
#include <iostream> #include <string> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <functional> #include <map> #include <set> #include <stack> #define FT(a, b) memset(a, b, sizeof(a)) #define FAT(a) memset(a, 0, sizeof(a)) using namespace std; typedef long long ll; const int M = 2e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 998244353; struct node { int dif; ll need; bool operator<(const node &f) const { if (f.need != need) return f.need > need; else return f.dif > dif; } } pro[M]; ll ans[M]; int main() { #ifdef ONLINE_JUDGE #else freopen("f:\\code\\c++\\in.txt", "r", stdin); #endif int t; scanf("%d", &t); while (t--) { FAT(ans); ll n, t, a, b; scanf("%lld%lld%lld%lld", &n, &t, &a, &b); ll simple = 0; for (int i = 1; i <= n; i++) { scanf("%d", &pro[i].dif); if (!pro[i].dif) simple++; } for (int i = 1; i <= n; i++) scanf("%lld", &pro[i].need); sort(pro + 1, pro + n + 1); ll time = 0; if (pro[1].need) ans[0] = min(simple, (pro[1].need - 1) / a); for (int i = 1; i <= n; i++) { if (pro[i].dif) time += b; else simple--, time += a; if (simple == 0 || i == n) break; ans[i] = min(simple, (pro[i + 1].need - time - 1) / a); } time = 0; ll cnt = ans[0]; for (int i = 1; i <= n; i++) { time += pro[i].dif == 0 ? a : b; if (time > t) break; else { if (time < pro[i + 1].need || i == n) { cnt = max(cnt, i + ans[i]); } } } printf("%lld\n", cnt); } return 0; }