Pinely Round 3 (Div. 1 + Div. 2)

Pinely Round 3 (Div. 1 + Div. 2)

Pinely Round 3 (Div. 1 + Div. 2)

A. Distinct Buttons

题意：当前处于(0, 0)原点，给出若干个平面坐标轴上的点，是否可以仅选择三个方向便可以到达所有给出的点。

思路：到达单一坐标点最多需要两个方向，记录到达每个点需要的方向，若四个方向都需要用到则不可能仅选择三个方向。

AC code：

void solve(){
    cin >> n;
    int x = 0, y = 0;
    int l = 0, r = 0, u = 0, d = 0;
    for(int i = 0; i < n; i ++){
        int t, v; cin >> t >> v;
        if(t < 0) l ++;
        if(t > 0) r ++;
        if(v > 0) u ++;
        if(v < 0) d ++;
    }
    if(l && r && u && d){
        cout << "NO" << endl;
        return;
    }cout << "YES" << endl;
}

B. Make Almost Equal With Mod

题意：给出一个长度为n的正整数数组a，现在必须选择一个正整数k，然后对于数组a中的每一个数将$a_i$替换为$a_i$mod k，该操作有且只有一次，在操作后，数组a中的元素必须有且仅有两个数不同，找出可能的k值。

思路：从二进制低位开始考虑k值，即从2开始考虑， 2的余数只有0或1两种可能，即二进制最低位是否为1，若2取余后均为同一数，说明二进制最低位要么全是0要么全是1，我们开始考虑次低位，以此类推，题目保证一定存在k值，所以从二进制最低位开始遍历。

k最大可能为1e18，则遍历的不会超过60位。

AC code：

void solve(){
    cin >> n;
    int x = 0, y = 0;
    int mn = 1e18;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 1; i <= 1e18; i *= 2){
        map<int, int> mp;
        for(int j = 1; j <= n; j ++)
            mp[a[j] % i] ++;
        if(mp.size() == 2){
            cout << i << endl;
            return;
        }
    }
}

C. Heavy Intervals

题意：给出左区间数组l和右区间数组r以及每个区间的权值数组c，现在需要将l和r进行任意匹配，保证每个区间的r>l，然后将权值数组c与每个区间进行配对，最终每个区间的权值为($r_i$-$l_i$)*$c_i$，现在需要最小化区间权重的总和。

思路：

首先所有区间的差加起来是恒定的，需要去分配这些差在每个区间的大小，然后在将小区间与大权值进行配对，那么现在问题在于如何找到最佳的区间。

这里需要将大区间尽可能的扩大，从而分配给更小的权值，然后相对的令小区间更小，分配给更大的权值，从而最小化区间权值总和。我们还需要保证每个区间都必须符合r>l的必须条件，所以不能盲目的用最大的r去匹配最小的l来最大化区间。

这里可以以右区间r为基准，因为要保证r>l，可以将左区间l排序后找到第一个小于r的数，然后将该数从l区间中删除，两种操作的最佳选择是set中的*prev(s.lower_bound?)（反转lower_bound函数，从寻找大于等于r的第一个元素变为寻找第一个小于r的元素）。

在匹配到每一对合法区间后，可以用pair进行存取，然后根据区间差进行升序排序（当然可以直接存区间差进行排序），然后对权值数组c进行降序排序，一一对应通过($r_i$-$l_i$)*$c_i$得到最后的最小区间权值和。

AC code：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 3e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n;
int l[N], r[N], c[N];
map<int, int> st;

bool cmp(PII a, PII b){
    return a.second - a.first < b.second - b.first;
}

void solve(){
    vector<PII> cnt;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> l[i];
    for(int i = 1; i <= n; i ++) cin >> r[i];
    for(int i = 1; i <= n; i ++) cin >> c[i];

    sort(l + 1, l + n + 1);
    sort(r + 1, r + n + 1);
    sort(c + 1, c + n + 1, greater<int>());

    set<int> s(l + 1, l + n + 1);
    for(int i = 1; i <= n; i ++){
        auto it = prev(s.lower_bound(r[i]));
        cnt.push_back({*it, r[i]});
        s.erase(it);
    }
    sort(cnt.begin(), cnt.end(), cmp);
    int ans = 0, t = 1;
    for(auto [x, y] : cnt){
        ans += (y - x) * c[t ++];
    }
    cout << ans << endl;
}

signed main(){
    fast();
    
    T = 1;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}