简答题 偏难
#20889

算法学习 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨计划学习 m 种算法,为此他找了 n 道题目来帮助自己学习,每道题目至多学习一次。 小…

算法学习

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨计划学习 m 种算法,为此他找了 n 道题目来帮助自己学习,每道题目至多学习一次。

小杨对于 m 种算法的初始掌握程度均为 0 。第 i 道题目有对应的知识点ai,即学习第 i 道题目可以令小杨对第ai种算法的掌握程度提高bi。小杨的学习目标是对 m 种算法的掌握程度均至少为 k 。

小杨认为连续学习两道相同知识点的题目是不好的,小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

输入格式

第一行三个正整数m,n,k,代表算法种类数,题目数和目标掌握程度。

第二行n个正整数a1,a2,a3,...,an,代表每道题目的知识点。

第二行n个正整数b1,b2,b3,...,bn,代表每道题目提升的掌握程度。

输出格式

输出一个整数,代表小杨最少需要学习题目的数量,如果不存在满足条件的方案,输出 -1。

输入样例1

3 5 10
1 1 2 3 3
9 1 10 10 1

输出样例1

1

输入样例2

2 4 10
1 1 1 2
1 2 7 10

输出样例2

-1

对于样例1,一种最优学习顺序为第一道题,第三道题,第四道题,第二道题。

对于全部数据,保证有1≤m,n≤105,1≤bi,k≤105,1≤ai≤m。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5 + 5; const int inf = 0x3f3f3f3f; int f[N]; vector&lt;int&gt; score[N + 2], a, b; bool cmp(int i, int j) { return i &gt; j; } int main() { int n, m, k; cin &gt;&gt; m &gt;&gt; n &gt;&gt; k; a.resize(n), b.resize(n); for (int i = 0; i &lt; n; i ++) cin &gt;&gt; a[i]; for (int i = 0; i &lt; n; i ++) { cin &gt;&gt; b[i]; score[a[i]].emplace_back(b[i]); } vector&lt;int&gt; need(m + 2); int ans = 0, mx_meed = 0, mx_need_i = -1; for (int i = 1; i &lt;= m; i ++) { sort(score[i].begin(), score[i].end(), cmp); int sum = 0; for (int j = 0; j &lt; (int) score[i].size(); j ++) { sum += score[i][j]; if (sum &gt;= k) { need[i] = j + 1; break ; } } if (sum &lt; k) { puts("-1"); return 0; } ans += need[i]; if (need[i] &gt; mx_meed) mx_meed = need[i], mx_need_i = i; } if (mx_meed - 1 &lt;= ans - mx_meed) { cout &lt;&lt; ans &lt;&lt; endl; return 0; } int last = 0; for (int i = 1; i &lt;= m; i ++) if (i != mx_need_i) last += score[i].size() - need[i]; cout &lt;&lt; (mx_meed - 1 &lt;= ans - mx_meed + last ? 2 * mx_meed - 1 : -1) &lt;&lt; endl; return 0; }</pre><p><br/></p>
解析

1.数据准备

读入数据,并将每道题目按知识点分类,记录每种算法通过题目提升掌握程度的列表score。

2.计算每种算法所需的题目数量

对于每种算法,我们需要计算达到目标掌握程度k所需的题目数量。为了最大化利用高分题目,我们需要按分数降序排序。

3.确定最少题目数量

我们需要找到一种安排,使得小杨学习的题目数量最少,并且避免连续学习相同知识点的题目。为此,我们找出需要题目最多的算法,并尝试调整学习顺序。

4.调整学习顺序

如果最多需要的题目数量mx_need减去1之后仍然不超过总需要的题目数量减去mx_need,那么可以通过调整顺序来满足要求;否则,输出-1。