leetcode第 70 场双周赛题解

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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处理出所有距离 ,按照鬼畜的偏序判断方法排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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划分一次,找到中间植物的数量,把这些数乘起来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}
};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!