leetcode weekly-contest-316

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

给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：

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 开始的数组 nums 和 cost ，分别包含 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;
}

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

给你两个正整数数组 nums 和 target ，两个数组长度相等。

在一次操作中，你可以选择两个不同的下标 i 和 j ，其中 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;
}

leetcode weekly-contest-316

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

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

使数组相等的最小开销

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

leetcode weekly-contest-310

AcWing Weekly-80

Paren

Comments | NOTHING

取消回复