Bouquet-Codeforces Round 961 (Div. 2)B2

题目大意: 有m块钱，买花只能买花瓣数差值不超过1的花，有多少花瓣就花多少钱，问最多能买到多少花瓣

分析: 赛时的时候就觉得是一个分类讨论，可惜没讨论出来, 策略是先只买一种，取$max$，如果存在$x+1$的花瓣数,先看能不能都买光. 如果不能买光，先买花瓣数为$x$的，买的个数是$g0=min(m/x,c[x])$代表着最多能买的个数和有的个数的最小值, 钱还有剩下的话买花瓣数为$x+1$的花，同理买$g1=min(c[x+1],(m-x\ast g0)/(x+1))$这么多，代表着有的花，和能买的花的最小值。 计算一下这样买了之后还剩下的钱$left$，如果说当前还可以买的花(花瓣数为x+1)和已经买的x的花大于等于left,说明可以用x+1代替x把钱花完，所以答案就是m 如果不可以的话，就替代min(g0,c[x+1]-g1),可能被替代的x和可以用来替代的x+1的最小值,答案取max

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n;i64 m;
void solve(){
    cin>>n>>m;
    vector<pair<i64,i64>> a(n);
    for(int i = 0;i<n;++i) cin>>a[i].first;
    for(int i = 0;i<n;++i) cin>>a[i].second;
    sort(a.begin(),a.end());
    i64 ans = 0;
    for(int i = 0;i<n;++i){
        ans = max(ans,min(m/a[i].first*a[i].first,a[i].first*a[i].second));
        if(i+1<n&&a[i].first+1==a[i+1].first){
            i64 r1 = a[i].first*a[i].second+a[i+1].first*a[i+1].second;
            if(r1<=m) ans = max(ans,r1);
            else{
                i64 g0 = min(a[i].second,m/a[i].first);
                i64 g1 = min(a[i+1].second,(m-g0*a[i].first)/a[i+1].first);
                i64 left = m-g0*a[i].first-g1*a[i+1].first;
                if(a[i+1].second-g1>=left&&g0>=left){
                    ans = max(ans,m);
                }else{
                    r1 = m-left+min(g0,a[i+1].second-g1);
                    ans = max(ans,r1);
                }
            }
        }
    }
    cout<<ans<<'\n';
}

signed main(){
    ios;
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Easy版本: easy版本我写了个长度为2的滑动窗口,限制条件有不超过m元，差值不为一，所以只要排个序，再写一个滑动窗口即可,时间复杂度$O(nlogn)$因为有排序