且听疯吟

kickstart 2021 round G

2022-11-20

kickstart 2021 round G

kickstart的算法果真还是非常的有难度,比力扣的难度大太多了.感觉还是智商不够，现在感觉 $\textit{leetcode}$ 上面只有 $\textit{hard}$ 题目比较感兴趣了，中等难度及以下，感觉基本上就是重复了。感觉每次比赛的第二题和第三题的质量非常高，非常适合新手练习和比赛．

problem B

With online classes in full swing, it is important for Grace to take breaks and keep herself hydrated at all times. She has decided to place a water bottle in her room in the most convenient place. This means that the position of this water bottle should be close to all the places in the room where she generally hangs out like the study desk, bed and coffee table among other places.

The room is represented in the form of a coordinate plane. The number of steps Grace needs to go from Point A to Point B is equal to the Manhattan distance between the 2 points. This means, Grace can only walk parallel to the axes of the coordinate plane and with each step, she can move one unit in either of the four directions.

Can you help her find a position in the room to keep the bottle, such that the sum of steps from the bottle to all her favourite furniture pieces will be minimum?

Notes:

  • All the furniture (like study desk, bed, or coffee table) can be represented as rectangles of non-zero area in the plane with edges parallel to the axes.
  • It is possible for furniture pieces to overlap, as she likes to work on her bed-table too.
  • Assume that Grace can simply pass through the furniture while walking and does not need to go around them.
    Input
    The first line of the input gives the number of test cases, T. T test cases follow.
    The first line of each test case contains an integer K which represents the number of objects in Grace’s room.
    K lines follow, each of them describing one object. The i-th line contains four integers, xi,1, yi,1, xi,2, yi,2, where (xi,1, yi,1) represents coordinates of the bottom left corner and (xi,2, yi,2) represents coordinates of the top right corner of the i-th rectangular object.
    Output
    For each test case, output one line containing Case #i: x y, where i is the test case number (starting from 1) and x and y are coordinates of the water bottle such that the sum of steps from these coordinates to all the furniture pieces will be minimum.
    Note, the bottle can lie on the floor or on top of any furniture but should be placed on integer coordinates only.
    If multiple solutions exist, output the one with minimum x coordinate, if multiple solutions have the same x coordinate output the one with minimum y coordinate.

地址

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b3a1c

题意

前缀和

思路

  1. 题意大概是说有一堆物体为长方形，散落在二维坐标系中，我们在二维坐标系中找打一个点使得该点到所有物体的曼哈顿距离之和最小．题目难度本身不是特别难，但是感觉有许多值得思考的地方，特别锻炼思维能力．
  2. 题目看似很难,实际上我们将曼哈顿距离分解为横坐标与总坐标,横坐标与纵坐标之间时间上处于独立的关系,因此我们可以分别求出横坐标与纵坐标.点$P=(x,y)$到矩形 $R$ 的曼哈顿距离计算公式为 $d(P,R) = max(x_{1}−x,x−x_{2},0) + max(y_{1}−y,y−y_{2},0)$, 其中矩形的左下端点为$(x_{1}, y_{1})$, 矩形的右上端点为$(x_{2}, y_{2})$.我们将所有的横坐标进行排列，假设分布如下：
    1
    对于给定的 $x$ 我们只需要找到所有右侧小于 $x$ 的矩形数目 $a(x)$, 以及找到所有左侧大于 $x$ 的矩形数目 $b(x)$.我们可以知道它的计算公式为:
    $$d(x) = (a(x)\times x - \sum_{j=0}^{a(x)}x_j) + (\sum_{i=0}^{b(x)}x_i - b(x)\times x) \qquad (x_j < x < x_i)$$
    对于给定的 $y$ 我们只需要找到所上边缘小于 $y$ 的矩形数目 $a(y)$, 以及找到所有下边缘大于 $y$ 的矩形数目 $b(y)$.我们可以知道它的计算公式为:
    $$d(y) = (a(y)\times y - \sum_{j=0}^{a(y)}y_j) + (\sum_{i=0}^{b(y)}y_i - b(y)\times y) \qquad (y_j < y < y_i)$$
  3. 我们可以找到最小的 $d(x) + d(y)$ 即可.我们可以依次遍历所有的可能的坐标，对于每个一个坐标 $x$ 我们依次求即可.
  4. 复杂度分析:
  • 时间复杂度: $O(N\lg(N))$,其中 $N$ 为所有矩形物品的数目.
  • 空间复杂度: $O(N)$,其中 $N$ 为所有矩形物品的数目.

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<limits.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void slove(int t){
    int k;
    ll x1,y1,x2,y2;
    ll x,y;
    
    cin>>k;
    vector<ll> px1;
    vector<ll> px2;
    vector<ll> py1;
    vector<ll> py2;
    vector<ll> sumx(k+1);
    vector<ll> sumy(k+1);
    vector<ll> arrx;
    vector<ll> arry;

    for(int i = 0; i < k; ++i) {
        cin>>x1>>y1>>x2>>y2;
        px1.push_back(x1);
        px2.push_back(x2);
        arrx.push_back(x1);
        arrx.push_back(x2);
        py1.push_back(y1);
        py2.push_back(y2);
        arry.push_back(y1);
        arry.push_back(y2);
    }
    ll distx = LLONG_MAX;
    ll disty = LLONG_MAX;
    sort(px1.begin(),px1.end());
    sort(px2.begin(),px2.end());
    sort(py1.begin(),py1.end());
    sort(py2.begin(),py2.end());
    sort(arrx.begin(),arrx.end());
    sort(arry.begin(),arry.end());
    for(int i = k-1; i >= 0; --i) {
        sumx[i] = sumx[i+1] + px1[i];
        sumy[i] = sumy[i+1] + py1[i];
    }
    ll pre = 0;
    ll l1 = 0;
    ll l2 = 0;
    for(int i = 0; i < arrx.size(); ++i){
        while(l2 < k && px2[l2] <= arrx[i]){
            pre += px2[l2];
            l2++;
        }
        while(l1 < k && px1[l1] <= arrx[i]) {
            l1++;
        }
        ll curr = l2*arrx[i] - pre + (sumx[l1] - (k-l1)*arrx[i]);
        if(curr < distx) {
            distx = curr;
            x = arrx[i];
        }
    }
    l1 = 0;
    l2 = 0;
    pre = 0;
    for(int i = 0; i < arry.size(); ++i){
        while (l2 < k && py2[l2] <= arry[i]) {
            pre += py2[l2];
            l2++;
        }
        while (l1 < k && py1[l1] <= arry[i]) {
            l1++;
        }
        ll curr = l2*arry[i] - pre + (sumy[l1] - (k-l1)*arry[i]);
        if(curr < disty) {
            disty = curr;
            y = arry[i];
        }
    }
    cout<<"Case #"<<t<<": ";
    cout<<x<<" "<<y;
    cout<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

problem C

题目

Problem
Barbara goes to Alan’s banana farm, where the N banana trees are organized in one long line represented by an array B. The tree at position i has Bi banana bunches. Each tree has the same cost. Once Barbara buys a tree, she gets all the banana bunches on that tree.
Alan has a special rule: because he does not want too many gaps in his line, he allows Barbara to buy at most 2 contiguous sections of his banana tree line.

Barbara wants to buy some number of trees such that the total number of banana bunches on these purchased trees equals the capacity K of her basket. She wants to do this while spending as little money as possible. How many trees should she buy?

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case begins with a line containing two integers integer N, the number of trees on Alan’s farm, and K, the capacity of Barbara’s basket.
The next line contains N non-negative integers $B1,B2,…,BN$ representing array B, where the i-th integer represents the number of banana bunches on the i-th tree on Alan’s farm.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of trees Barbara must purchase to obtain K banana bunches using at most 2 contiguous sections of the farm, or -1 if it is impossible to do so.

地址

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b44ef

题意

数组

思路

  1. 这个题目虽然不是很难, 但是感觉出的非常好.题目要求找到最多两个非重复的连续子序列的和等于 $k$ 的最短长度,我们设 $dp[i]$ 表示连续子序列的和等于 $i$ 的最短长度.
  2. 我们每次从 $i$ 开始往后遍历, 找到从 $i$ 到 $n$ 的连续子序列的和等于 $x$ 的最短长度. 我们从 $i$ 往前开始往前遍历,依次遍历每一个截至到 $i$ 的连续子序列的和 $curr$ ,同时我们从 $i+1$ 往后找到 $dp[k-curr]$.

    我们找到递推公式如下:
    $$ dp[k] = min(dp[k], x + d[k-i])$$
  3. 复杂度分析:
  • 时间复杂度分析: 时间复杂度为 $O(n\times k)$ , 其中 $n$ 为数组的长度, $k$ 为目标要求的和.
  • 空间复杂度分析: 空间复杂度为$O(k)$．

代码

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<string.h>

using namespace std;

void slove(int t){
    int n,k;
    vector<int> arr;

    cin>>n>>k;
    arr = vector<int>(n);
    for(int i = 0; i < n; ++i){
        cin>>arr[i];
    }

    vector<int> dp(k+1,n+1);
    dp[0] = 0;
    for(int i = n - 1; i >= 0; --i) {
        long long curr = 0;
        for(int j = i; j >= 0; --j) {
            curr += arr[j];
            if(curr <= k) {
                dp[k] = min(dp[k],dp[k-curr]+i+1-j);
            }
        }
        curr = 0;
        for(int j = i; j < n; ++j) {
            curr += arr[j];
            if(curr <= k){
                dp[curr] = min(dp[curr],j+1-i);
            }
        }
    }
    cout<<"Case #"<<t<<": ";
    cout<<(dp[k] > n ? -1 : dp[k])<<endl;
}

int main(){
    int t;
    cin>>t;
    for(int i = 0; i < t; ++i){
        slove(i+1);
    }
    return 0;
}

欢迎关注和打赏，感谢支持！

Tags: kickstart
← 贪吃蛇 【kickstart】 kickstart 2021 roundC →

扫描二维码，分享此文章