leetcode weekly-contest-316

发布于 2022-10-23  589 次阅读


判断两个事件是否存在冲突

给你两个字符串数组 event1event2 ,表示发生在同一天的两个闭区间时间段事件,其中:

  • event1 = [startTime1, endTime1]
  • event2 = [startTime2, endTime2]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时(即,某些时刻是两个事件都包含的),则认为出现 冲突

如果两个事件之间存在冲突,返回 true ;否则,返回 false

示例 1:

输入:event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
输出:true
解释:两个事件在 2:00 出现交集。

示例 2:

输入:event1 = ["01:00","02:00"], event2 = ["01:20","03:00"]
输出:true
解释:两个事件的交集从 01:20 开始,到 02:00 结束。

示例 3:

输入:event1 = ["10:00","11:00"], event2 = ["14:00","15:00"]
输出:false
解释:两个事件不存在交集。

提示:

  • evnet1.length == event2.length == 2.
  • event1[i].length == event2[i].length == 5
  • startTime1 <= endTime1
  • startTime2 <= endTime2
  • 所有事件的时间都按照 HH:MM 格式给出

随便搞一搞模拟一下就出来了。

#include <bits/stdc++.h>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
class Solution {
public:
    int gao(string s){
        return stoi(s.substr(0,2))*60+ stoi(s.substr(3));
    }
    bool v[1440];
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        rep(i,gao(event1[0]), gao(event1[1])+1) v[i]=1;
        rep(i,gao(event2[0]),gao(event2[1])+1) if(v[i]) return true;
        return false;
    }
};

void solve() {

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

最大公因数等于 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1:

输入:nums = [9,3,1,2,6,3], k = 3
输出:4
解释:nums 的子数组中,以 3 作为最大公因数的子数组如下:
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2:

输入:nums = [4], k = 7
输出:0
解释:不存在以 7 作为最大公因数的子数组。

提示:

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

namo一眼就可以确定数据范围是可暴力的范围,再大就要线段树gcd了

#include <bits/stdc++.h>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

class Solution {
public:
    int subarrayGCD(vector<int> &nums, int k) {
        int ans = 0;
        rep(i, 0, sz(nums)) {
            int g = nums[i];
            rep(j, i, sz(nums)) {
                g = __gcd(g, nums[j]);
                if (g == k)
                    ans++;
            }
        }
        return ans;
    }
};

void solve() {

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

使数组相等的最小开销

给你两个下标从 0 开始的数组 numscost ,分别包含 n 整数。

你可以执行下面操作 任意 次:

  • nums任意 元素增加或者减小 1

对第 i 个元素执行一次操作的开销是 cost[i]

请你返回使 nums 中所有元素 相等最少 总开销。

示例 1:

输入:nums = [1,3,5,2], cost = [2,3,1,14]
输出:8
解释:我们可以执行以下操作使所有元素变为 2 :
- 增加第 0 个元素 1 次,开销为 2 。
- 减小第 1 个元素 1 次,开销为 3 。
- 减小第 2 个元素 3 次,开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。

示例 2:

输入:nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出:0
解释:数组中所有元素已经全部相等,不需要执行额外的操作。

提示:

  • n == nums.length == cost.length
  • 1 <= n <= 105
  • 1 <= nums[i], cost[i] <= 106

namo可以很好的证明一个不等式,设x是最终的数,那么有

$$
Q=\sum_{i=0}^{sz(nums)}abs(x-nums[i])*cost[i]
$$

可以转换到板子题如果改变一个数的成本为1,那么要多少个,也就是把nums[i]换成了cost[i],最终结论就是都到中位数

#include <bits/stdc++.h>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

class Solution {
public:
    long long minCost(vector<int> &nums, vector<int> &cost) {
        vector<pii> m(sz(nums));
        rep(i, 0, sz(nums)) m[i] = {nums[i], cost[i]};
        sort(all(m));
        ll sum = Sum(cost);
        int cnt = -1;
        ll pre = 0;
        rep(i, 0, sz(m)) {
            pre += m[i].se;
            if (pre >= sum / 2) {
                cnt = m[i].fi;
                break;
            }
        }
        ll ans = 0;
        each(p, m) {
            ans += 1ll * p.se * abs(p.fi - cnt);
        }
        return ans;
    }
};

void solve() {

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

使数组相似的最少操作次数

给你两个正整数数组 numstarget ,两个数组长度相等。

在一次操作中,你可以选择两个 不同 的下标 ij ,其中 0 <= i, j < nums.length ,并且:

  • nums[i] = nums[i] + 2
  • nums[j] = nums[j] - 2

如果两个数组中每个元素出现的频率相等,我们称两个数组是 相似 的。

请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。

示例 1:

输入:nums = [8,12,6], target = [2,14,10]
输出:2
解释:可以用两步操作将 nums 变得与 target 相似:
- 选择 i = 0 和 j = 2 ,nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ,nums = [10,14,2] 。
2 次操作是最少需要的操作次数。

示例 2:

输入:nums = [1,2,5], target = [4,1,3]
输出:1
解释:一步操作可以使 nums 变得与 target 相似:
- 选择 i = 1 和 j = 2 ,nums = [1,4,3] 。

示例 3:

输入:nums = [1,1,1,1,1], target = [1,1,1,1,1]
输出:0
解释:数组 nums 已经与 target 相似。

提示:

  • n == nums.length == target.length
  • 1 <= n <= 105
  • 1 <= nums[i], target[i] <= 106
  • nums 一定可以变得与 target 相似。

因为都+2,-2,所以奇数偶数分组搞一下,不变位置已处理就出来了。

这个咋证明我还想不起来了。。设abc和efg对应,如果不是按排序不等式的顺序搞,那么一定是乱序和,顺序和>乱序和>反序和。排序不等式出来的。

#include <bits/stdc++.h>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

class Solution {
public:
    long long makeSimilar(vector<int> &nums, vector<int> &target) {
        sort(all(nums), [&](int &a, int &b) {
            if (a % 2 == b % 2) { return a < b; }
            return a % 2 < b % 2;
        });
        sort(all(target), [&](int &a, int &b) {
            if (a % 2 == b % 2) { return a < b; }
            return a % 2 < b % 2;
        });
        ll ans = 0;
        rep(i, 0, sz(nums)) {
            ans += abs(nums[i] - target[i]);
        }
        return ans / 4;
    }
};

void solve() {

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

绝对不是恋爱脑!