企业官网建设流程全解析

视频讲解：[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。

输入输出样例

输入 #1

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

输出 #1

4

输入 #2

2 4 10 1 1 1 2 1 2 7 10

输出 #2

-1

说明/提示

样例 1 解释

一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。

数据规模与约定

对于全部数据，保证有 1≤m,n,bi​,k≤10^5，1≤ai​≤m。

二、做题思路

1)填充数据

#include<bits/stdc++.h> using namespace std; const int arr_m=100005; map<int,vector<int>> storage; int m,n,k; int main(){ //1)填充数据 //1.1)确定算法种类m 题目数量n 掌握程度k cin>>m>>n>>k; //1.2)填充n题的对应知识点 int temp[arr_m]={}; for(int i=1;i<=n;i++) cin>>temp[i]; //1.3)填充n题的提升 for(int i=1;i<=n;i++){ int t;cin>>t; storage[temp[i]].push_back(t); } return 0; }

2)贪心：先用提升高的题

2.1)循环每个知识点

#include<bits/stdc++.h> using namespace std; const int arr_m=100005; map<int,vector<int>> storage; int m,n,k; bool cmp(int a,int b){ return a>b; } int check(){ int maxx=0,ans=0,maxx_i; //2.1)循环每个知识点 for(int i=1;i<=m;i++){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); } } int main(){ //1)填充数据 //... //2)贪心：先用提升高的题 cout<<check(); return 0; }

2.2)检查当前知识点达标至少需要多少题

#include<bits/stdc++.h> using namespace std; const int arr_m=100005; map<int,vector<int>> storage; int m,n,k; bool cmp(int a,int b){ return a>b; } int check(){ int maxx=0,ans=0,maxx_i; //2.1)循环每个知识点 for(int i=1;i<=m;i++){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); //2.2)检查当前知识点达标至少需要多少题 int sum=0,count=0; for(auto it:storage[i]){ sum+=it; count++; if(sum>=k) break; } //无法达标 if(sum<k) return -1; } } int main(){ //1)填充数据 //... //2)贪心：先用提升高的题 cout<<check(); return 0; }

2.3)避免连续学习

#include<bits/stdc++.h> using namespace std; const int arr_m=100005; map<int,vector<int>> storage; int m,n,k; bool cmp(int a,int b){ return a>b; } int check(){ int maxx=0,ans=0,maxx_i; //2.1)循环每个知识点 for(int i=1;i<=m;i++){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); //2.2)检查当前知识点达标至少需要多少题 int sum=0,count=0; for(auto it:storage[i]){ sum+=it; count++; if(sum>=k) break; } //无法达标 if(sum<k) return -1; //2.3)避免连续学习 //2.3.1)找最大值 if(maxx<count){ maxx=count; maxx_i=i; } //2.3.2)找最大值 //累加题目数量 ans+=count; } //2.3.3)最大知识点-1<=最小其他知识点之和 if(maxx-1<=ans-maxx){ return ans; }else if(maxx-1<=n-storage[maxx_i].size()){//2.3.4)最大知识点-1<=其他知识点之和 return maxx*2-1; } return -1; } int main(){ //1)填充数据 //... //2)贪心：先用提升高的题 cout<<check(); return 0; }

三、答案

#include<bits/stdc++.h> using namespace std; const int arr_m=100005; map<int,vector<int>> storage; int m,n,k; bool cmp(int a,int b){ return a>b; } int check(){ int maxx=0,ans=0,maxx_i; //2.1)循环每个知识点 for(int i=1;i<=m;i++){ //排序 sort(storage[i].begin(),storage[i].end(),cmp); //2.2)检查当前知识点达标至少需要多少题 int sum=0,count=0; for(auto it:storage[i]){ sum+=it; count++; if(sum>=k) break; } //无法达标 if(sum<k) return -1; //2.3)避免连续学习 //2.3.1)找最大值 if(maxx<count){ maxx=count; maxx_i=i; } //2.3.2)找最大值 //累加题目数量 ans+=count; } //2.3.3)最大知识点-1<=最小其他知识点之和 if(maxx-1<=ans-maxx){ return ans; }else if(maxx-1<=n-storage[maxx_i].size()){//2.3.4)最大知识点-1<=其他知识点之和 return maxx*2-1; } return -1; } int main(){ //1)填充数据 //1.1)确定算法种类m 题目数量n 掌握程度k cin>>m>>n>>k; //1.2)填充n题的对应知识点 int temp[arr_m]={}; for(int i=1;i<=n;i++) cin>>temp[i]; //1.3)填充n题的提升 for(int i=1;i<=n;i++){ int t;cin>>t; storage[temp[i]].push_back(t); } //2)贪心：先用提升高的题 cout<<check(); return 0; }