[GESP202409 六级] 算法学习（含视频）

视频讲解[GESP202409 六级] 算法学习-信息学奥赛GESP等级考试真题解析一、原题题目描述小杨计划学习 m 种算法为此他找了 n 道题目来帮助自己学习每道题目最多学习一次。小杨对于 m 种算法的初始掌握程度均为 0。第 i 道题目有对应的知识点 ai​即学习第 i 道题目可以令小杨对第 ai​ 种算法的掌握程度提高 bi​。小杨的学习目标是对于 m 种算法的掌握程度均至少为 k。小杨认为连续学习两道相同知识点的题目是不好的小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。输入格式第一行三个正整数 m,n,k代表算法种类数题目数和目标掌握程度。第二行 n 个正整数 a1​,a2​,...,an​代表每道题目的知识点。第三行 n 个正整数 b1​,b2​,...,bn​代表每道题目提升的掌握程度。输出格式输出一个整数代表小杨最少需要学习题目的数量如果不存在满足条件的方案输出 -1。输入输出样例输入 #13 5 10 1 1 2 3 3 9 1 10 10 1输出 #14输入 #22 4 10 1 1 1 2 1 2 7 10输出 #2-1说明/提示样例 1 解释一种最优学习顺序为第一道题第三道题第四道题第二道题。数据规模与约定子任务编号数据点占比mnbi​k130%2≤9≤10≤10230%≤9≤9≤10≤10340%≤10^5≤10^5≤10^5≤10^5对于全部数据保证有 1≤m,n,bi​,k≤10^51≤ai​≤m。二、做题思路1)填充数据#includebits/stdc.h using namespace std; const int arr_m100005; mapint,vectorint storage; int m,n,k; int main(){ //1)填充数据 //1.1)确定算法种类m 题目数量n 掌握程度k cinmnk; //1.2)填充n题的对应知识点 int temp[arr_m]{}; for(int i1;in;i) cintemp[i]; //1.3)填充n题的提升 for(int i1;in;i){ int t;cint; storage[temp[i]].push_back(t); } return 0; }2)贪心先用提升高的题2.1)循环每个知识点#includebits/stdc.h using namespace std; const int arr_m100005; mapint,vectorint storage; int m,n,k; bool cmp(int a,int b){ return ab; } int check(){ int maxx0,ans0,maxx_i; //2.1)循环每个知识点 for(int i1;im;i){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); } } int main(){ //1)填充数据 //... //2)贪心先用提升高的题 coutcheck(); return 0; }2.2)检查当前知识点达标至少需要多少题#includebits/stdc.h using namespace std; const int arr_m100005; mapint,vectorint storage; int m,n,k; bool cmp(int a,int b){ return ab; } int check(){ int maxx0,ans0,maxx_i; //2.1)循环每个知识点 for(int i1;im;i){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); //2.2)检查当前知识点达标至少需要多少题 int sum0,count0; for(auto it:storage[i]){ sumit; count; if(sumk) break; } //无法达标 if(sumk) return -1; } } int main(){ //1)填充数据 //... //2)贪心先用提升高的题 coutcheck(); return 0; }2.3)避免连续学习#includebits/stdc.h using namespace std; const int arr_m100005; mapint,vectorint storage; int m,n,k; bool cmp(int a,int b){ return ab; } int check(){ int maxx0,ans0,maxx_i; //2.1)循环每个知识点 for(int i1;im;i){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); //2.2)检查当前知识点达标至少需要多少题 int sum0,count0; for(auto it:storage[i]){ sumit; count; if(sumk) break; } //无法达标 if(sumk) return -1; //2.3)避免连续学习 //2.3.1)找最大值 if(maxxcount){ maxxcount; maxx_ii; } //2.3.2)找最大值 //累加题目数量 anscount; } //2.3.3)最大知识点-1最小其他知识点之和 if(maxx-1ans-maxx){ return ans; }else if(maxx-1n-storage[maxx_i].size()){//2.3.4)最大知识点-1其他知识点之和 return maxx*2-1; } return -1; } int main(){ //1)填充数据 //... //2)贪心先用提升高的题 coutcheck(); return 0; }三、答案#includebits/stdc.h using namespace std; const int arr_m100005; mapint,vectorint storage; int m,n,k; bool cmp(int a,int b){ return ab; } int check(){ int maxx0,ans0,maxx_i; //2.1)循环每个知识点 for(int i1;im;i){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); //2.2)检查当前知识点达标至少需要多少题 int sum0,count0; for(auto it:storage[i]){ sumit; count; if(sumk) break; } //无法达标 if(sumk) return -1; //2.3)避免连续学习 //2.3.1)找最大值 if(maxxcount){ maxxcount; maxx_ii; } //2.3.2)找最大值 //累加题目数量 anscount; } //2.3.3)最大知识点-1最小其他知识点之和 if(maxx-1ans-maxx){ return ans; }else if(maxx-1n-storage[maxx_i].size()){//2.3.4)最大知识点-1其他知识点之和 return maxx*2-1; } return -1; } int main(){ //1)填充数据 //1.1)确定算法种类m 题目数量n 掌握程度k cinmnk; //1.2)填充n题的对应知识点 int temp[arr_m]{}; for(int i1;in;i) cintemp[i]; //1.3)填充n题的提升 for(int i1;in;i){ int t;cint; storage[temp[i]].push_back(t); } //2)贪心先用提升高的题 coutcheck(); return 0; }