简答题
偏难
#12883
刷任务 题目描述 一共有 n 个小任务,第 i 个任务会消耗 a i 点体力、 b i 点心神。 你可以自由安排任务的完成顺序,逐个依次做完任务。 当累计消耗的…
刷任务
题目描述
一共有 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
限制
时间限制:1000ms
内存限制:256MiB
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。