跳转至

weekly-contest-327

A

Statement

Metadata

给你一个按 非递减顺序 排列的数组 nums ,返回正整数数目和负整数数目中的最大值。

  • 换句话讲,如果 nums 中正整数的数目是 pos ,而负整数的数目是 neg ,返回 posneg二者中的最大值。

注意:0 既不是正整数也不是负整数。

 

示例 1:

输入:nums = [-2,-1,-1,1,2,3]
输出:3
解释:共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2:

输入:nums = [-3,-2,-1,0,0,1,2]
输出:3
解释:共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 3:

输入:nums = [5,20,66,1314]
输出:4
解释:共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

 

提示:

  • 1 <= nums.length <= 2000
  • -2000 <= nums[i] <= 2000
  • nums非递减顺序 排列。

Metadata

Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.

  • In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

Note that 0 is neither positive nor negative.

 

Example 1:

Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.

Example 2:

Input: nums = [-3,-2,-1,0,0,1,2]
Output: 3
Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.

Example 3:

Input: nums = [5,20,66,1314]
Output: 4
Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.

 

Constraints:

  • 1 <= nums.length <= 2000
  • -2000 <= nums[i] <= 2000
  • nums is sorted in a non-decreasing order.

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    int maximumCount(vector<int> &nums) {
        int pos = 0;
        int neg = 0;
        for (const auto &a : nums) {
            if (a > 0) {
                ++pos;
            }

            if (a < 0) {
                ++neg;
            }
        }

        return max(pos, neg);
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

B

Statement

Metadata

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数0

在一步 操作 中:

  1. 选出一个满足 0 <= i < nums.length 的下标 i
  2. 将你的 分数 增加 nums[i] ,并且
  3. nums[i] 替换为 ceil(nums[i] / 3)

返回在 恰好 执行 k 次操作后,你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

 

示例 1:

输入:nums = [10,10,10,10,10], k = 5
输出:50
解释:对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

示例 2:

输入:nums = [1,10,3,3,3], k = 3
输出:17
解释:可以执行下述操作:
第 1 步操作:选中 i = 1 ,nums 变为 [1,4,3,3,3] 。分数增加 10 。
第 2 步操作:选中 i = 1 ,nums 变为 [1,2,3,3,3] 。分数增加 4 。
第 3 步操作:选中 i = 2 ,nums 变为 [1,1,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。

 

提示:

  • 1 <= nums.length, k <= 105
  • 1 <= nums[i] <= 109

Metadata

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

  1. choose an index i such that 0 <= i < nums.length,
  2. increase your score by nums[i], and
  3. replace nums[i] with ceil(nums[i] / 3).

Return the maximum possible score you can attain after applying exactly k operations.

The ceiling function ceil(val) is the least integer greater than or equal to val.

 

Example 1:

Input: nums = [10,10,10,10,10], k = 5
Output: 50
Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.

Example 2:

Input: nums = [1,10,3,3,3], k = 3
Output: 17
Explanation: You can do the following operations:
Operation 1: Select i = 1, so nums becomes [1,4,3,3,3]. Your score increases by 10.
Operation 2: Select i = 1, so nums becomes [1,2,3,3,3]. Your score increases by 4.
Operation 3: Select i = 2, so nums becomes [1,1,1,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.

 

Constraints:

  • 1 <= nums.length, k <= 105
  • 1 <= nums[i] <= 109

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    long long maxKelements(vector<int> &nums, int k) {
        priority_queue<int> pq;
        for (const auto &a : nums) {
            pq.push(a);
        }

        ll res = 0;
        while (k && !pq.empty()) {
            int x = pq.top();
            pq.pop();

            res += x;
            int y = (x + 2) / 3;
            if (y > 0) {
                pq.push((x + 2) / 3);
            }

            --k;
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

C

Statement

Metadata

给你两个下标从 0 开始的字符串 word1word2

一次 移动 由以下两个步骤组成:

  • 选中两个下标 ij ,分别满足 0 <= i < word1.length0 <= j < word2.length
  • 交换 word1[i]word2[j]

如果可以通过 恰好一次 移动,使 word1word2 中不同字符的数目相等,则返回 true ;否则,返回 false

 

示例 1:

输入:word1 = "ac", word2 = "b"
输出:false
解释:交换任何一组下标都会导致第一个字符串中有 2 个不同的字符,而在第二个字符串中只有 1 个不同字符。

示例 2:

输入:word1 = "abcc", word2 = "aab"
输出:true
解释:交换第一个字符串的下标 2 和第二个字符串的下标 0 。之后得到 word1 = "abac" 和 word2 = "cab" ,各有 3 个不同字符。

示例 3:

输入:word1 = "abcde", word2 = "fghij"
输出:true
解释:无论交换哪一组下标,两个字符串中都会有 5 个不同字符。

 

提示:

  • 1 <= word1.length, word2.length <= 105
  • word1word2 仅由小写英文字母组成。

Metadata

You are given two 0-indexed strings word1 and word2.

A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].

Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.

 

Example 1:

Input: word1 = "ac", word2 = "b"
Output: false
Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.

Example 2:

Input: word1 = "abcc", word2 = "aab"
Output: true
Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.

Example 3:

Input: word1 = "abcde", word2 = "fghij"
Output: true
Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.

 

Constraints:

  • 1 <= word1.length, word2.length <= 105
  • word1 and word2 consist of only lowercase English letters.

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    bool isItPossible(string word1, string word2) {
        auto diff = vector<int>(5, 0);
        auto cnt = vector<vector<int>>(2, vector<int>(50, 0));
        auto words = vector<string>({word1, word2});

        for (int i = 0; i < 2; i++) {
            const auto &w = words[i];
            for (const auto &c : w) {
                ++cnt[i][c - 'a'];
                if (cnt[i][c - 'a'] == 1) {
                    ++diff[i];
                }
            }
        }

        if (diff[0] < diff[1]) {
            swap(diff[0], diff[1]);
            swap(cnt[0], cnt[1]);
        }

        for (int i = 0; i < 30; i++) {
            for (int j = 0; j < 30; j++) {
                if (cnt[0][i] == 0 || cnt[1][j] == 0) {
                    continue;
                }

                auto diff_ = diff;

                if (cnt[0][i] == 1) {
                    --diff_[0];
                }

                --cnt[0][i];

                if (cnt[0][j] == 0) {
                    ++diff_[0];
                }
                ++cnt[0][j];

                if (cnt[1][i] == 0) {
                    ++diff_[1];
                }

                ++cnt[1][i];

                if (cnt[1][j] == 1) {
                    --diff_[1];
                }
                --cnt[1][j];

                if (diff_[0] == diff_[1]) {
                    return true;
                }

                ++cnt[0][i];
                --cnt[0][j];
                --cnt[1][i];
                ++cnt[1][j];
            }
        }

        return false;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

D

Statement

Metadata

共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 nk,以及一个二维整数数组 time ,数组的大小为 k x 4 ,其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi]

一条河将两座仓库分隔,只能通过一座桥通行。旧仓库位于河的右岸,新仓库在河的左岸。开始时,所有 k 位工人都在桥的左侧等待。为了移动这些箱子,第 i 位工人(下标从 0 开始)可以:

  • 从左岸(新仓库)跨过桥到右岸(旧仓库),用时 leftToRighti 分钟。
  • 从旧仓库选择一个箱子,并返回到桥边,用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。
  • 从右岸(旧仓库)跨过桥到左岸(新仓库),用时 rightToLefti 分钟。
  • 将箱子放入新仓库,并返回到桥边,用时 putNewi 分钟。不同工人可以同时放下所选的箱子。

如果满足下面任一条件,则认为工人 i效率低于 工人 j

  • leftToRighti + rightToLefti > leftToRightj + rightToLeftj
  • leftToRighti + rightToLefti == leftToRightj + rightToLeftji > j

工人通过桥时需要遵循以下规则:

  • 如果工人 x 到达桥边时,工人 y 正在过桥,那么工人 x 需要在桥边等待。
  • 如果没有正在过桥的工人,那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待,那么 效率最低 的工人会先过桥。
  • 如果没有正在过桥的工人,且桥右边也没有在等待的工人,同时旧仓库还剩下至少一个箱子需要搬运,此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待,那么 效率最低 的工人会先过桥。

所有 n 个盒子都需要放入新仓库,请你返回最后一个搬运箱子的工人 到达河左岸 的时间。

 

示例 1:

输入:n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]
输出:6
解释:
从 0 到 1 :工人 2 从左岸过桥到达右岸。
从 1 到 2 :工人 2 从旧仓库搬起一个箱子。
从 2 到 6 :工人 2 从右岸过桥到达左岸。
从 6 到 7 :工人 2 将箱子放入新仓库。
整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间,所以返回 6 。

示例 2:

输入:n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]
输出:50
解释:
从 0 到 10 :工人 1 从左岸过桥到达右岸。
从 10 到 20 :工人 1 从旧仓库搬起一个箱子。
从 10 到 11 :工人 0 从左岸过桥到达右岸。
从 11 到 20 :工人 0 从旧仓库搬起一个箱子。
从 20 到 30 :工人 1 从右岸过桥到达左岸。
从 30 到 40 :工人 1 将箱子放入新仓库。
从 30 到 31 :工人 0 从右岸过桥到达左岸。
从 31 到 39 :工人 0 将箱子放入新仓库。
从 39 到 40 :工人 0 从左岸过桥到达右岸。
从 40 到 49 :工人 0 从旧仓库搬起一个箱子。
从 49 到 50 :工人 0 从右岸过桥到达左岸。
从 50 到 58 :工人 0 将箱子放入新仓库。
整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间,所以返回 50 。

 

提示:

  • 1 <= n, k <= 104
  • time.length == k
  • time[i].length == 4
  • 1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000

Metadata

There are k workers who want to move n boxes from an old warehouse to a new one. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi].

The warehouses are separated by a river and connected by a bridge. The old warehouse is on the right bank of the river, and the new warehouse is on the left bank of the river. Initially, all k workers are waiting on the left side of the bridge. To move the boxes, the ith worker (0-indexed) can :

  • Cross the bridge from the left bank (new warehouse) to the right bank (old warehouse) in leftToRighti minutes.
  • Pick a box from the old warehouse and return to the bridge in pickOldi minutes. Different workers can pick up their boxes simultaneously.
  • Cross the bridge from the right bank (old warehouse) to the left bank (new warehouse) in rightToLefti minutes.
  • Put the box in the new warehouse and return to the bridge in putNewi minutes. Different workers can put their boxes simultaneously.

A worker i is less efficient than a worker j if either condition is met:

  • leftToRighti + rightToLefti > leftToRightj + rightToLeftj
  • leftToRighti + rightToLefti == leftToRightj + rightToLeftj and i > j

The following rules regulate the movement of the workers through the bridge :

  • If a worker x reaches the bridge while another worker y is crossing the bridge, x waits at their side of the bridge.
  • If the bridge is free, the worker waiting on the right side of the bridge gets to cross the bridge. If more than one worker is waiting on the right side, the one with the lowest efficiency crosses first.
  • If the bridge is free and no worker is waiting on the right side, and at least one box remains at the old warehouse, the worker on the left side of the river gets to cross the bridge. If more than one worker is waiting on the left side, the one with the lowest efficiency crosses first.

Return the instance of time at which the last worker reaches the left bank of the river after all n boxes have been put in the new warehouse.

 

Example 1:

Input: n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]
Output: 6
Explanation: 
From 0 to 1: worker 2 crosses the bridge from the left bank to the right bank.
From 1 to 2: worker 2 picks up a box from the old warehouse.
From 2 to 6: worker 2 crosses the bridge from the right bank to the left bank.
From 6 to 7: worker 2 puts a box at the new warehouse.
The whole process ends after 7 minutes. We return 6 because the problem asks for the instance of time at which the last worker reaches the left bank.

Example 2:

Input: n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]
Output: 50
Explanation: 
From 0  to 10: worker 1 crosses the bridge from the left bank to the right bank.
From 10 to 20: worker 1 picks up a box from the old warehouse.
From 10 to 11: worker 0 crosses the bridge from the left bank to the right bank.
From 11 to 20: worker 0 picks up a box from the old warehouse.
From 20 to 30: worker 1 crosses the bridge from the right bank to the left bank.
From 30 to 40: worker 1 puts a box at the new warehouse.
From 30 to 31: worker 0 crosses the bridge from the right bank to the left bank.
From 31 to 39: worker 0 puts a box at the new warehouse.
From 39 to 40: worker 0 crosses the bridge from the left bank to the right bank.
From 40 to 49: worker 0 picks up a box from the old warehouse.
From 49 to 50: worker 0 crosses the bridge from the right bank to the left bank.
From 50 to 58: worker 0 puts a box at the new warehouse.
The whole process ends after 58 minutes. We return 50 because the problem asks for the instance of time at which the last worker reaches the left bank.

 

Constraints:

  • 1 <= n, k <= 104
  • time.length == k
  • time[i].length == 4
  • 1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

struct Node {};

class Solution {
public:
    int findCrossingTime(int n, int k, vector<vector<int>> &time) {}
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

最后更新: October 11, 2023
回到页面顶部