【题目描述】 在一条街道上有n栋楼，第i栋有hi层，每层都有价值为vi的物品。Lyra可以花费一单位时间在同一栋楼中向上或向下走一层。特别地，每栋楼里都有一个大滑梯，只能从顶楼通往一楼，所以如果Lyra在顶层，可以花费一单位时间通过滑梯到达一楼（注意只有在顶楼才可以使用滑梯）。
Lyra还可以在不同的楼之间跳跃，即花费一单位时间从当前楼移动到相邻楼的同层，如果相邻楼没有Lyra当前位置高，则会落到相邻楼的顶层。
初始时Lyra在第一栋楼的顶层，她有m单位时间可以移动，Lyra拿去物品不需要时间，且一个物品被拿一次之后就会消失。Lyra想知道她能获得的总价值最多是多少？ 【输入】 第一行两个正整数n,m 以下n行每行两个整数表示hi和vi
提示：输入数据较大，请采用快速的读入方式。 【输出】
输出一行一个整数表示最大的总价值。 【输入样例】
3 3 2 1 1 5 3 4【输出样例】
14解题思路：
核心思想是怎样求最大值，这里是按着第一栋，第1,2栋，第1,2,3栋的顺序， 先是只在第一栋楼里活动，然后判断时间是否超过； 当第2,3栋的时候，如果第二栋的价值比第一栋的大，这就要考虑要不要把第一栋全部换为第二栋（这里考虑换的时候还有两种情况：即是可以全部换，还是只需换一部分）； 第1,2,3栋的时候亦是如此。 可以参考下鱼塘钓鱼的题目 没想到第一篇题解竟是这么难的题，qwq #include<bits/stdc++.h> using namespace std; #define ll long long #define val first #define high second priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>que; ll n, m; const int M = 1000000; ll h[M + 5], v[M + 5]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> h[i] >> v[i]; h[i]--;//每一楼的第一个是不用花时间的 //即如第一栋有7层，从顶层到底层只需7-1个单位时间 } ll sum = 0; ll ans = 0; ll maxn = 0; for (int k = 1; k <= n; k++) { //按着第一栋，第一栋和第二栋，第1,2,3栋的顺序来 ans += v[k];//在这一栋楼，如第2栋，就直接加上价值，跳到这楼上的时候 if (sum + h[k] <= m) {//此时没有取满，就直接加上 //此时的第二栋的h[i]已经-1，上面加了 sum += h[k];//时间 ans += h[k] * v[k]; que.push(make_pair(v[k], h[k])); }//注意，这里如果没满的话，直接进入到下一层循环，如题目中的 //第二栋只需一次即可。 else {//当此时已经超过时间，就要判断没有加的 //楼和前面已加的楼的方案 pair<ll, ll>a; a = que.top(); while (a.val < v[k] && (!que.empty())) { //如果前一栋楼的数值比现在的小，则把前面一栋的全部换掉（最好） if (sum + h[k] - a.high >= m) {//如果我把前面的 //一栋楼用现在的楼代替还大于m //说明要跟其前前面的楼比较 //把之前的楼删掉 que.pop(); ans = ans - a.high * a.val; sum -= a.high; } else {//如果全部替换后还有多于的时间 //就说明之前的楼只需要丢掉一部分使 //新加的刚好等于m que.pop(); int mid = sum + h[k] - m;//看多出了几层 ans = ans - mid * a.val; //减去多出的层数 a.high -= mid; sum -= mid; que.push(a); break; } a = que.top(); } int mark = m - sum; //求出需要填充几层 pair<ll, ll>q; q.val = v[k]; q.high = mark; if (q.high) { que.push(q); ans = ans + q.val * q.high; sum = m; } } if (ans > maxn) maxn = ans; m--; //每次到下一栋楼就要花费1个单位时间 } cout << maxn; return 0; }这题主要运用了贪心算法，虽然不是几个典型的题，但也算是经典，这题也是类似的就只是题解多了点。楼间跳跃这题我好像只找到了2篇，算上我这一篇，我还是借鉴于(https://blog.csdn.net/stldecember/article/details/93976721)。
最后附上贪心算法的讲解：五大常用算法入门–贪心算法
