![《P11247 [GESP202409 六级] 算法学习》](http://pic.xiahunao.cn/yaotu/《P11247 [GESP202409 六级] 算法学习》)
题目背景对应的选择、判断题试题 - GESP 202409 C 六级 - 洛谷有题题目描述小杨计划学习 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 解释一种最优学习顺序为第一道题第三道题第四道题第二道题。数据规模与约定子任务编号数据点占比mnbik130%2≤9≤10≤10230%≤9≤9≤10≤10340%≤105≤105≤105≤105对于全部数据保证有 1≤m,n,bi,k≤1051≤ai≤m。代码实现#include bits/stdc.h using namespace std; typedef long long ll; const int MAXM 1e5 10; vectorll group[MAXM]; int low[MAXM]; int maxcnt[MAXM]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; ll k; cin m n k; vectorint a(n); vectorll b(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin b[i]; for (int i 0; i n; i) { group[a[i]].push_back(b[i]); } bool impossible false; ll S 0; int M 0; int max_pos -1; for (int t 1; t m; t) { auto vec group[t]; maxcnt[t] vec.size(); sort(vec.rbegin(), vec.rend()); ll sum 0; int need -1; for (int i 0; i vec.size(); i) { sum vec[i]; if (sum k) { need i 1; break; } } if (need -1) { impossible true; } low[t] need; S need; if (need M) { M need; max_pos t; } } if (impossible) { cout -1 endl; return 0; } ll other S - M; ll ans; if (M other 1) { ans S; } else { ll d M - (other 1); ll avail 0; for (int t 1; t m; t) { if (t max_pos) continue; avail maxcnt[t] - low[t]; } if (avail d) { ans S d; } else { cout -1 endl; return 0; } } cout ans endl; return 0; }
题目背景对应的选择、判断题试题 - GESP 202409 C 六级 - 洛谷有题题目描述小杨计划学习 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 解释一种最优学习顺序为第一道题第三道题第四道题第二道题。数据规模与约定子任务编号数据点占比mnbik130%2≤9≤10≤10230%≤9≤9≤10≤10340%≤105≤105≤105≤105对于全部数据保证有 1≤m,n,bi,k≤1051≤ai≤m。代码实现#include bits/stdc.h using namespace std; typedef long long ll; const int MAXM 1e5 10; vectorll group[MAXM]; int low[MAXM]; int maxcnt[MAXM]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; ll k; cin m n k; vectorint a(n); vectorll b(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin b[i]; for (int i 0; i n; i) { group[a[i]].push_back(b[i]); } bool impossible false; ll S 0; int M 0; int max_pos -1; for (int t 1; t m; t) { auto vec group[t]; maxcnt[t] vec.size(); sort(vec.rbegin(), vec.rend()); ll sum 0; int need -1; for (int i 0; i vec.size(); i) { sum vec[i]; if (sum k) { need i 1; break; } } if (need -1) { impossible true; } low[t] need; S need; if (need M) { M need; max_pos t; } } if (impossible) { cout -1 endl; return 0; } ll other S - M; ll ans; if (M other 1) { ans S; } else { ll d M - (other 1); ll avail 0; for (int t 1; t m; t) { if (t max_pos) continue; avail maxcnt[t] - low[t]; } if (avail d) { ans S d; } else { cout -1 endl; return 0; } } cout ans endl; return 0; }
