5971. 打折购买糖果的最小开销

从大到小排序，三个三个买(2个花钱，1个赠送)，剩余的不够三个就直接花钱买下剩余全部的。

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.begin(),cost.end(),greater<int>());
        int n = cost.size();
        int ans = 0;

        for(int i = 0;i < n;i ++)
        {
            ans += cost[i];
            i++;
            if(i<n) ans += cost[i];
            else break;
            i++;
            if(i<n) ans += 0;
            else break;
        }

        return ans;
    }
};

5972. 统计隐藏数组数目

设第一个元素为x，差分数组的前缀和最小值为minnd，最大为maxxd，那么x + minnd 就是数组最小的元素l(此时x是下界)，x + maxxd就是数组中最大的元素r(此时x是上界)。

所以x的范围是 l - minnd 到r - maxxd。

但是需要注意的是: l - minnd 可能会小于l，因此左边界为max(l - minnd, 1ll*l);

同理右边界为: min(r - maxxd,1ll*r);

typedef long long ll;
class Solution {
public:
    int numberOfArrays(vector<int>& d, int l, int r) {
        int n = d.size();
        ll minnd = 1e9;
        ll maxxd = -1e9;
        ll now = 0;
        for(int i=0;i<n;i++)
        {
            now = now + 1ll*d[i];
            minnd = min(minnd,now);
            maxxd = max(maxxd,now);
        }
        ll x  = max(l - minnd, 1ll*l);
        ll y = min(r - maxxd,1ll*r);
        return (int)max(y - x + 1,1ll*0);
    }
};

5973. 价格范围内最高排名的 K 样物品

恶心的马力题，bfs处理出所有距离 ，按照鬼畜的偏序判断方法排序即可。

#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=998244353;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};


class Solution {
public:
    map<pii,int>dis;
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& g, vector<int>& p, vector<int>& s, int k) {
        int n = g.size();
        int m = g[0].size();
        queue<pii>q;
        q.push({s[0],s[1]});
        dis[{s[0],s[1]}] = 0;
        while(!q.empty())
        {
            pii f = q.front();
            q.pop();
            int x = f.first, y = f.second;
            if(dis.count(f))
            {
                for(int i=0;i<4;i++)
                {
                    int xx = x + di[i];
                    int yy = y + dj[i];
                    if(xx>=0&&xx<n&&yy>=0&&yy<m&&g[xx][yy]!=1&&(!dis.count({xx,yy})))
                    {
                        dis[{xx,yy}] = dis[f] + 1;
                        q.push({xx,yy});
                    }
                }

            }
        }
        vector<vector<int>>res;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(g[i][j]>=p[0]&&g[i][j]<=p[1])
                {
                    res.push_back({dis[{i,j}], g[i][j], i, j});
                    cout<<dis[{i,j}] <<" "<< g[i][j]<<" "<<i<<" "<< j<<endl;
                }
            }
        }
        sort(res.begin(),res.end());
        vector<vector<int>>ans;
        for(int i=0;i<k;i++)
        {
            ans.push_back({res[i][2],res[i][3]});
        }
        return ans;
    }
};

5974. 分隔长廊的方案数

每两个s划分一次，找到中间植物的数量，把这些数乘起来即可。

#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=1e9+7;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};

class Solution {
public:
    int numberOfWays(string s) {
        int n = s.size();
        ll ans = 1;
        int beg = 0;
        for(beg=0;beg<n;beg++)
        {
            if(s[beg]=='S') break;
        }
        int ed = n-1;
        for(ed=n-1;ed>=0;ed--)
        {
            if(s[ed]=='S') break;
        }
        int scnt = 0;
        bool ok = false;
        for(int i = beg;i <= ed; i++)
        {
            if(scnt<2&&s[i]=='S') scnt++;
            if(scnt==2)
            {
                ok = true;
                int pcnt = 0;
                i++;
                while(i<=ed&&s[i]!='S')
                {
                    pcnt++;
                    i++;
                }
                ans = ans*(pcnt+1)%MOD;
                scnt = 0;
                i--;
            }
        }
        
        if(!ok||scnt!=0) ans = 0;
        return (int)ans;
    }
};