首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; using ll = long long; struct Task { ll a, b; }; int n; ll X, Y; vector&lt;Task&gt; t, ta, tb; vector&lt;ll&gt; sa, sb; // 按a升序 bool cmpA(const Task &amp;x, const Task &amp;y) { return x.a &lt; y.a; } // 按b升序 bool cmpB(const Task &amp;x, const Task &amp;y) { return x.b &lt; 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) &lt;= X; // b排序后缀和 ll sumB = 0; vector&lt;ll&gt; sbb(n + 1, 0); for (int i = n - 1; i &gt;= 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) &lt;= Y; bool cond3 = (sumA &gt; X) || (sumB &gt; Y); return cond1 &amp;&amp; cond2 &amp;&amp; cond3; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin &gt;&gt; n &gt;&gt; X &gt;&gt; Y; t.resize(n); for (int i = 0; i &lt; n; ++i) cin &gt;&gt; t[i].a; for (int i = 0; i &lt; n; ++i) cin &gt;&gt; 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 &gt;= 0; --i) { sa[i] = sa[i + 1] + ta[i].a; } int l = 1, r = n, ans = n; while (l &lt;= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } cout &lt;&lt; ans &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。