A17459. 刷任务
填空题
困难
知识点
题目描述
刷任务
题目描述
一共有 n 个小任务，第 i 个任务会消耗 ai 点体力、bi 点心神。
你可以自由安排任务的完成顺序，逐个依次做完任务。
当累计消耗的体力总和超过 xx，或是 累计消耗的心神总和超过 y 时，会立刻停下无法继续做事。
求：在运气最差、顺序最不利的情况下，你最少会完成多少个任务就被迫停止。
输入格式
第一行，三个整数表示 n, x, y
第二行，n 个整数表示 a1,a2,…,an
第三行，n 个整数表示 b1,b2,…,bn
输出格式
输出一个整数，表示最少完成的任务数量。
输入样例#1
4 7 18
2 3 5 1
8 8 1 4输出样例#1
2输入样例#2
8 30 30
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1输出样例#2
6说明提示
1≤n≤2×105
1≤x,y≤2×1014
1≤ai,bi≤109
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
struct Task {
ll a, b;
};
int n;
ll X, Y;
vector<Task> t, ta, tb;
vector<ll> sa, sb;
// 按a升序
bool cmpA(const Task &x, const Task &y) {
return x.a < y.a;
}
// 按b升序
bool cmpB(const Task &x, const Task &y) {
return x.b < y.b;
}
bool check(int k) {
if (k == 0) return false;
// a排序后缀和
int pos = n - k;
ll sumA = sa[pos];
ll minA = ta[pos].a;
bool cond1 = (sumA - minA) <= X;
// b排序后缀和
ll sumB = 0;
vector<ll> sbb(n + 1, 0);
for (int i = n - 1; i >= 0; i--) sbb[i] = sbb[i + 1] + tb[i].b;
pos = n - k;
sumB = sbb[pos];
ll minB = tb[pos].b;
bool cond2 = (sumB - minB) <= Y;
bool cond3 = (sumA > X) || (sumB > Y);
return cond1 && cond2 && cond3;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> X >> Y;
t.resize(n);
for (int i = 0; i < n; ++i) cin >> t[i].a;
for (int i = 0; i < n; ++i) cin >> t[i].b;
ta = t; tb = t;
sort(ta.begin(), ta.end(), cmpA);
sort(tb.begin(), tb.end(), cmpB);
// 预处理a后缀和
sa.assign(n + 1, 0);
sb.assign(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
sa[i] = sa[i + 1] + ta[i].a;
}
int l = 1, r = n, ans = n;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}
上一题
下一题