CCF GESP 202309 C++五六级另解选讲

大家好，欢迎来到IT知识分享网。

1. 【GESP C++五级】巧夺大奖

这是本次C++五级的第二道编程题。有的同学可能已经看过官方的题解了，这里介绍另一种解题思路：按时间顺序来模拟玩游戏的过程。先把所有的游戏按时间段从小到大排序，那么优先去选那些时间即将截止的游戏，才能尽可能的不错过游戏。若所有游戏的截止时间段都没有冲突的，那我们就按照时间顺序一个个玩就好了；若在同一个截止时间段，有多个游戏时怎么办？因为不能同时玩，只需看一下前面有没有空的时间段，若有的话直接插到前面去玩也行。

若前面都满了没有空可插该怎么办呢？这时候需要看一下现在这个游戏的奖励是否足够大。具体地说，跟前面已经玩过的游戏去比，看值不值得放弃前面奖励小的游戏，而换成这个奖励更大的游戏。如果值得去换，应该尽量去换前面奖励最小的游戏，从而使得总奖励最高。到这里，我们就需要维护一个前面已玩游戏的奖励的最小值，一个数据结构便呼之欲出，那就是小根堆（优先队列，二叉堆）。即每次有时间段冲突的时候，比较当前游戏的奖励值与堆顶的最小奖励值，看是否值得去更换游戏。

总体难度系数普及-，代码细节如下：

#include <bits/stdc++.h> using namespace std; int n, ans; priority_queue<int, vector<int>, greater<int> > pri_que; struct game { int t, r; }G[505]; bool cmp(game x, game y) { return x.t < y.t; } int main() { cin>>n; for(int i = 1; i <= n; ++i) cin>>G[i].t; for(int i = 1; i <= n; ++i) cin>>G[i].r; sort(G+1, G+n+1, cmp); for(int i = 1; i <= n; ++i) { if(pri_que.size() < G[i].t) { ans += G[i].r; pri_que.push(G[i].r); } else if(G[i].r > pri_que.top()) { ans -= pri_que.top(); pri_que.pop(); ans += G[i].r; pri_que.push(G[i].r); } } cout<<ans<<endl; return 0; }

2.【GESP C++六级】小杨买饮料

这是本次C++六级的第一道编程题，典型的背包问题。背包问题有很多变式，也有很多简化的方法（降维、滚动数组等）。下面从初学者二维动态规划的视角出发，解析一下这道题。

首先看一下数据范围，N最大为500，L最大为2000，定义二维状态dp[i][j]表示从前i个饮料中购买至少j毫升饮料的最少花费。当面对第i+1个饮料（价格为c，容量为l）时:

可以不购买，那么dp[i+1][j] = dp[i][j]；

也可以购买，dp[i+1][j] = dp[i][j-l] + c;

取上述中的最小值，得到状态转移如下：

dp[i][j] = min(dp[i-1][j], dp[i-1][j-l] + c);

代码实现时，还要再注意下上述j和l的大小关系。

总体难度系数普及-，具体代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 505; const int MAXL = 2005; int N, L, c[MAXN], l[MAXN], dp[MAXN][MAXL]; int main() { cin>>N>>L; for(int i = 1; i <= N; ++i) { cin>>c[i]>>l[i]; } memset(dp, 0x3f, sizeof(dp)); for(int j = 1; j <= min(l[1],L); ++j) dp[1][j] = c[1]; for(int i = 2; i <= N; ++i) { for(int j = 1; j <= L; ++j) { dp[i][j] = dp[i-1][j]; if(l[i] >= j) dp[i][j] = min(dp[i][j], c[i]); else dp[i][j] = min(dp[i][j], dp[i-1][j-l[i]] + c[i]); } } if(dp[N][L] == 0x3f3f3f3f) cout<<"no solution"<<endl; else cout<<dp[N][L]<<endl; return 0; }