再次翻车了

第四个卡精度搞了好久好久,,还是看了讨论区才处理精度问题的。。

第三个纯属自己代码写的太丑了,脑子不够清晰吧。赛后1分钟ac。。。

image-20210530121215404

5772. 检查某单词是否等于两单词之和

简单模拟, 不过我这里写的太麻烦了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool isSumEqual(string firstWord, string secondWord, string targetWord) {
int a = 0, b = 0, t = 0;
for(auto c: firstWord) {
a = a*10 + (c-'a');
}
for(auto c: secondWord) {
b = b*10 + (c-'a');
}
for(auto c: targetWord) {
t = t*10 + (c-'a');
}
return a+b == t;
}
};

5773. 插入后的最大值

正负情况讨论一下就好了,

正数:

想要值最大就把这个数字放到第一个比他的数字前面

负数

想要值最大就把这个数字放到第一个比他的数字前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string maxValue(string n, int x) {
string ans;
if(n[0] == '-') {
for(auto c: n) {
if(x!=0 && c!='-' && c-'0' > x) {ans += '0'+x;x=0;}
ans += c;
}
} else {
for(auto c: n) {
if(x!=0 && c-'0' < x) {ans += '0'+x;x=0;}
ans += c;
}
}

if(x != 0) ans += '0'+x;

return ans;
}
};

5774. 使用服务器处理任务

这里维护两个优先队列就好了,

一个维护tuple<int, int> 表示 权重,下标。这个就是空闲的服务器队列

另一个维护tuple<int, int, int> 表示 任务处理的时间,权重,下标。这个就是正在处理任务的服务器队列

过程中维护一个时间就行了, 如果空闲队列为空,就从非空闲的队列中吧做完任务的拿出来,如果没有做完的就调大下时间。

这里好像有卡长,我最开始写的比较丑,是++time这样玩儿的,因为值域是2e52e5 所以这里++time的次数应该也是线性的才对,理论上不会增大复杂度的。

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
class Solution {
public:
vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> q1; // weight, index
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int> > > q2; // time, weight, index.

int idx = 0;
for(auto server: servers) {
q1.push({server, idx++});
}

vector<int> ans;

int time = 0;
int p = 0;
for(; p <= time && p<tasks.size(); p++) {
int &task = tasks[p];

if(q1.empty()) time = max(time, std::get<0>(q2.top()));
while(!q2.empty() && std::get<0>(q2.top()) <= time) {
auto [t, w, i] = q2.top(); q2.pop();
q1.push({w, i});
}

auto [weight, index] = q1.top(); q1.pop();
q2.push({time+task, weight, index});
ans.push_back(index);

if(p >= time) time = max(time+1, p);
}

return ans;
}
};

5775. 准时抵达会议现场的最小跳过休息次数

又是一个DP,,

不过这个DP很简单

dp[i][j]表示前i个道路 跳过j个所花的时间

转移就是

cur=dist[i]speed;dp[i][j]=max(dp[i1][j1]+cur,dp[i1][j]+cur)cur = \frac{dist[i]}{speed}; \\ dp[i][j] = max(dp[i-1][j-1] + cur, \lceil dp[i-1][j] \rceil + cur)


因为浮点数精度问题, 所以我这里改了下

dp[i][j]表示前i个道路 跳过j个 “行进” 距离,

转移就是

cur=dist[i];dp[i][j]=max(dp[i1][j1]+cur,dp[i1][j]speed×speed+cur)cur = dist[i]; \\ dp[i][j] = max(dp[i-1][j-1] + cur, \lceil \frac{dp[i-1][j]}{speed} \rceil \times speed + cur)

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
class Solution {
public:
typedef long long int LL;
LL dp[1001][1001]; // 前i个道路 跳过j个的 “行进”距离,
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
int n = dist.size();

for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j] = 1e14;

dp[0][0] = 0;
for(int i=1; i<=n; i++) {
LL cur = dist[i-1];

dp[i][0] = (dp[i-1][0]+speed-1)/speed*speed + cur;

for(int j = 1; j<i; j++) {
dp[i][j] = min(dp[i][j],
min(dp[i-1][j-1] + cur,
(dp[i-1][j]+speed-1)/speed*speed + cur));
}
}

int ans = -1;
for(int i=0;i<=n;i++) {
if(dp[n][i] <= 1LL * hoursBefore * speed) {
ans = i;
break;
}
}
return ans;
}
};