牛客月赛-环上食虫

原题链接

题目描述

牛牛参加了牛妹的派对。
牛牛面前有一个圆桌，圆桌边缘按顺序摆上了 n 个蛋糕（第一个蛋糕和第 n 个蛋糕相邻）。
每个蛋糕都有一个饱腹值和奶油含量。
牛牛不喜欢吃奶油，所以他想要在保证自己能吃饱（所吃蛋糕的饱腹度的和大于等于 s）的情况下，所选择的蛋糕中奶油含量最大的那一个的奶油含量越低越好。我们知道，牛牛一直都是个绅士。所以他选择的蛋糕应该是相邻的（也就是对应圆上的一段弧（也可以是整个圆））。
现在它想请你帮它计算在能够吃饱的情况下，他吃到蛋糕中奶油含量最高的那一个最低会是多少？

输入样例

5 9
4 3 7 6 1
1 3 9 2 5

输出样例

5

---

算法

(双指针 + 环问题 + 求区间最大值)

本题由于每次枚举的是一个区间的左边界 l 与右边界 r，而从左边界到右边界的整个区间是只要满足饱腹度之和大于等于 s 即可且r 必定在 l 之后，所以每次随着 l 的移动 r 的枚举是不断递增的，不用重新从l + 1 开始枚举，所以主要应用双指针算法。

双指针:注意其实饱腹度>=s的情况下，区间越短越好(注意边界r的问题)。

环问题:复制原数组，判断区间确实对应环上的一段。

求区间最大值: 用multiset（注意multiset.end()指向的是最后一位的下一位地址）。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
ll n,s;
ll w[N],val[N];

int main()
{
    cin >> n >> s;
    for (int i = 1;i <= n;i ++ ) {
        cin >> w[i];
        w[i + n] = w[i];
    }
    for (int i = 1;i <= n;i ++ ) {
        cin >> val[i];
        val[i + n] = val[i];
    } 
    
    multiset<ll> st;
    ll res =1e10,sum = 0;
    bool ok = false;
    for (ll l = 1,r = 0;l <= n;l ++ ) {//注意r加到哪里放到哪里
        while (sum < s && r < 2 * n) {
            r ++;
            sum += w[r];
            st.insert(val[r]);//也可以st.insert(-val[r]);
        }
        if (sum >= s && r - l + 1 <= n) {
            ok = true;
            res = min(res,*(--st.end()));//也可以res = min(res,-(*st.begin()))
        }
        sum -= w[l];
        st.erase(st.find(val[l]));//也可以st.earse(st.find(-val[l]))
    }
    
    if (!ok) puts("-1"); 
    else cout << res << '\n';
    return 0;
}