第 28周双周赛

Posted on | In , | |
Words count in article: 466 | Reading time ≈ 2

5420. 商品折扣后的最终价格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int> res;
        for(int i=0; i<prices.size(); i++) {
            int cur = prices[i];
            for(int j=i+1; j<prices.size(); j++) {
                if(prices[j] <= cur) {
                    cur -= prices[j];
                    break;
                }
            }
            res.push_back(cur);
        }
        return res;
    }
};

5422. 子矩形查询

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
class SubrectangleQueries {
public:
    vector<vector<int>> cur;
    
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        cur = rectangle;
    }
    
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1; i<=row2; i++) {
            for(int j=col1; j<=col2; j++) {
                cur[i][j] = newValue;
            }
        }
    }
    
    int getValue(int row, int col) {
        return cur[row][col];
    }
};

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
 * obj->updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj->getValue(row,col);
 */

5423. 找两个和为目标值且不重叠的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    unordered_map<int, int> mp;
    int f[100005];
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int sum = 0;
        mp[0] = 0;
        int n = arr.size(), ans = 0x3f3f3f3f;
        memset(f, 0x3f, sizeof(f));
        for (int i = 1; i <= n; ++i){
            sum += arr[i - 1];
            int gp = sum - target;
            f[i] = f[i - 1];
            if (mp.count(gp)){
                int pos = mp[gp];
                f[i] = min(f[i], i - pos);
                ans = min(ans, i - pos + f[pos]);
            }
            mp[sum] = i;
        }
        return ans == 0x3f3f3f3f ? -1: ans;
    }
};

5421. 安排邮筒

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
class Solution {
    long long f[105][105];
    long long dis[105][105];
public:
    int minDistance(vector<int>& houses, int k) {
        int n = houses.size();
        sort(houses.begin(), houses.end());
        for (int i = 1; i <= n; ++i){
            for (int j = i; j <= n; ++j){
                int p = (j - i) >> 1;
                int mid = i + p;
                int pos = houses[mid - 1];
                long long res = 0;
                for (int t = i; t <= j; ++t)
                    res += abs(houses[t - 1] - pos);
                dis[i][j] = res;
            }
        }
        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i){
            for (int t = 1; t <= i && t <= k; ++t){
                for (int j = i - 1; j >= 0; --j)
                    f[i][t] = min(f[i][t], f[j][t - 1] + dis[j + 1][i]);
            }
        }
        return f[n][k];
    }
};
Donate? comment?