某方案以球员k1结尾

发布时间：2025-06-24 18:11:55  作者：北方职教升学中心  阅读量：363

如果k1的能力小于等于k2，则此方案加上i2一定不会冲突。子墨子言之：事无终始，无务多业。球队的得分是球队中所有球员的分数 总和 。分数最小的位1,次小的为2$\cdots$。
将年龄离散化，方便处理比当前队员年龄小的队员。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。注意，你可以选中多个同龄球员。
提示：
1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 10⁶
1 <= ages[i] <= 1000

动态规划+离散化

将分数离散化，并用nums记录原始分数。

代码

核心代码

classSolution{public:intbestTeamScore(vector<int>&scores,vector<int>&ages){constintN =scores.size();{autotmp =ages;tmp.emplace_back(0);CDiscretize dis(tmp);for(auto&i :ages){i =dis[i];}}constintM =*max_element(ages.begin(),ages.end());autotmp =scores;tmp.emplace_back(0);CDiscretize dis(tmp);for(auto&i :scores){i =dis[i];}vector<int>index(N);iota(index.begin(),index.end(),0);sort(index.begin(),index.end(),[&](inti1,inti2){return(ages[i1]<ages[i2])||((ages[i1]==ages[i2])&&(scores[i1]<scores[i2]));});vector<vector<int>>dp(M +1,vector<int>(N +1));intans =0;for(intk :index){constinti =ages[k];intj =scores[k];dp[i][j]=max(dp[i -1][j],dp[i][j])+dis.m_nums[j];ans =max(ans,dp[i][j]);for(j =1;j <=N;j++){dp[i][j]=max(dp[i][j],dp[i][j -1]);dp[i][j]=max(dp[i][j],dp[i-1][j ]);}}returnans;}};

单元测试

vector<int>scores,ages;TEST_METHOD(TestMethod1){scores ={3,2,4},ages ={1,2,3};autores =Solution().bestTeamScore(scores,ages);AssertEx(7,res);}TEST_METHOD(TestMethod11){scores ={1,3,5,10,15},ages ={1,2,3,4,5};autores =Solution().bestTeamScore(scores,ages);AssertEx(34,res);}TEST_METHOD(TestMethod12){scores ={4,5,6,5},ages ={2,1,2,1};autores =Solution().bestTeamScore(scores,ages);AssertEx(16,res);}TEST_METHOD(TestMethod13){scores ={1,2,3,5},ages ={8,9,10,1};autores =Solution().bestTeamScore(scores,ages);AssertEx(6,res);}TEST_METHOD(TestMethod14){scores ={1,1,1},ages ={3,2,1};autores =Solution().bestTeamScore(scores,ages);AssertEx(3,res);}TEST_METHOD(TestMethod15){scores ={1,1,1},ages ={1,3,5};autores =Solution().bestTeamScore(scores,ages);AssertEx(3,res);}TEST_METHOD(TestMethod16){scores ={1,1,1,1,1,1,1,1,1,1},ages ={811,364,124,873,790,656,581,446,885,134};autores =Solution().bestTeamScore(scores,ages);AssertEx(10,res);}TEST_METHOD(TestMethod17){scores ={6,5,1,7,6,5,5,4,10,4},ages ={3,2,5,3,2,1,4,4,5,1};autores =Solution().bestTeamScore(scores,ages);AssertEx(43,res);}

优化

i1 < i2 ，k1 = index[i1] ,k2 = index[i2]。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。
示例 2：
输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。也就是我们常说的专业的人做专业的事。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
某方案以球员k1结尾。时间复杂度：O(nlogn)
直接枚举时间复杂度：O(nn)

代码

classCDiscretize//离散化{public:CDiscretize(vector<int>nums){sort(nums.begin(),nums.end());nums.erase(std::unique(nums.begin(),nums.end()),nums.end());m_nums =nums;for(inti =0;i <nums.size();i++){m_mValueToIndex[nums[i]]=i;}}intoperator[](constintvalue)const{autoit =m_mValueToIndex.find(value);if(m_mValueToIndex.end()==it){return-1;}returnit->second;}intsize()const{returnm_mValueToIndex.size();}vector<int>m_nums;protected:unordered_map<int,int>m_mValueToIndex;};classSolution{public:intbestTeamScore(vector<int>&scores,vector<int>&ages){constintN =scores.size();CDiscretize dis(scores);for(auto&i :scores){i =dis[i];}vector<int>index(N);iota(index.begin(),index.end(),0);sort(index.begin(),index.end(),[&](inti1,inti2){return(ages[i1]<ages[i2])||((ages[i1]==ages[i2])&&(scores[i1]<scores[i2]));});vector<int>dp(N +1);intans =0;for(intk :index){constinti =ages[k];intj =scores[k];constintiMax =*max_element(dp.begin(),dp.begin()+j +1);dp[j]=max(dp[j],iMax +dis.m_nums[j]);ans =max(ans,dp[j]);}returnans;}};

扩展阅读

for(j =1;j <=N;j++){dp[i][j]=max(dp[i][j],dp[i][j -1]);dp[i][j]=max(dp[i][j],dp[i-1][j ]);}

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
示例 3：
输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
故只需枚举能力小于等于当前能力的球员。同龄球员之间不会发生矛盾。