# leetcode weekly-contest-316

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

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

输入：event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]

输入：event1 = ["01:00","02:00"], event2 = ["01:20","03:00"]

输入：event1 = ["10:00","11:00"], event2 = ["14:00","15:00"]

• 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 = [9,3,1,2,6,3], k = 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]

输入：nums = [4], k = 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;
}


## 使数组相等的最小开销

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

输入：nums = [1,3,5,2], cost = [2,3,1,14]

- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。

输入：nums = [2,2,2,2,2], cost = [4,2,8,1,3]

• 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]$$

#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[i] = nums[i] + 2
• nums[j] = nums[j] - 2

输入：nums = [8,12,6], target = [2,14,10]

- 选择 i = 0 和 j = 2 ，nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ，nums = [10,14,2] 。
2 次操作是最少需要的操作次数。

输入：nums = [1,2,5], target = [4,1,3]

- 选择 i = 1 和 j = 2 ，nums = [1,4,3] 。

输入：nums = [1,1,1,1,1], target = [1,1,1,1,1]

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

#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;
}