枚举，二分，前缀和

前缀和

ABC181E: Transformable Teacher

1200

题意

\(N \le 2 \times 10^5\) (奇数)个小朋友，第 \(i\) 身高为 \(H_i\) ，老师的身高可以变换，共有\(M \le 2 \times 10^5\) 种形态，第 \(i\) 种身高为 \(W_i\) . 现在小朋友和老师一起做游戏，两个人一组。配对花费为 \[ \sum_{i=1}^{(N+1)/2}|x_i-y_i| \] \(x_i,y_i\) 是第 \(i\) 组两个人的身高

求最小的的配对花费。

分析

老师必定要匹配一个小朋友。那么可以枚举小朋友和老师匹配，剩下的小朋友自己匹配。自己匹配的最优解一定是排序后两个相邻的匹配。小朋友和老师匹配，就是老师选一个和小朋友最接近的升高来匹配。这个可以排序后用二分 \(O(logM)\) 实现。小朋友两两匹配可以用前缀和预处理好, 枚举的时候 \(O(1)\) 查询.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m;
ll H[maxn], W[maxn];
ll suml[maxn], sumr[maxn];

ll getmin(ll x) {
    auto pos = lower_bound(W+1, W+m+1, x) - W;
    ll ret = abs(x - W[pos]);
    if (pos > 1) ret = min(ret, abs(x - W[pos-1]));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n; ++i) {
        cin >> H[i];   
    }
    for (int i = 1;i <= m; ++i) {
        cin >> W[i];
    }
    sort(H+1, H+n+1);
    sort(W+1, W+m+1);
    for (int i = 1;i <= n; ++i) { // 向左匹配的总消费
        if (i % 2 == 0) suml[i] = abs(H[i] - H[i-1]) + suml[i-2];
    }
    for (int i = n;i >= 1; --i) { // 向右匹配的总消费
        if (i % 2 == 0) sumr[i] = abs(H[i] - H[i+1]) + sumr[i+2];
    }
    ll ans = 1e18;
    for (int i = 1;i <= n; ++i) {
        if (i % 2 == 0) 
            ans = min(ans, suml[i-2] + sumr[i+2] + abs(H[i-1] - H[i+1]) + getmin(H[i]));
        else
            ans = min(ans, suml[i-1] + sumr[i+1] + getmin(H[i]));
    }
    cout << ans << endl;
    return 0;
}

枚举

AGC048B. Bracket Score

题意

一个括号匹配序列只有 () 和 [] , 他们不能交叉比如这样不行， ([)]也不能缺少匹配 [() . 现在有两个数组 \(A, B\) ，它的长度和某个括号匹配序列一致。在每个对应位置，如果是 () 就选择 \(A\) 数组的元素， 如果是 [] 中的某个就选 \(B\) 的元素。总价值是所有选出元素的和。问选怎样的括号匹配序列才能使价值最大化

分析

首先，我们发现每个括号内的元素个数一定是偶数，因为如果是奇数的话就不能匹配。然后我们反过来想，如果我选出的元素都满足这个条件：相同数组的数之间的数的个数是偶数，是不是一定可以写出一个合法的序列。然后发现是可以的。这个条件也就是奇数位置的数只能匹配偶数的数（否则之间的数就不是偶数了）。假设我们全部选择 \(B\) ,然后我们一步步优化。我们把 \(A_i-B_i\) 存在数组里面。考虑贪心：我们每次从奇数位置选一个最大的，偶数位置选最大的一对。每次更新一下答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


ll n, m, A[maxn], B[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        cin >> A[i];
    }
    ll sum = 0;
    vector<ll> odd, even;
    
    for (int i = 1;i <= n; ++i) {
        cin >> B[i];
        sum += B[i];
        if (i % 2) odd.push_back(A[i] - B[i]);
        else even.push_back(A[i] - B[i]);
    }
    ll ans = sum;
    sort(odd.begin(), odd.end(), greater<>());
    sort(even.begin(), even.end(), greater<>());
    for (int i = 0;i < sz(odd); ++i) {
        sum += odd[i] + even[i];
        ans = max(sum, ans);
    }
    cout << ans << endl;
    return 0;
}

1408D Searchlights

按 \(x\) 排序，二维枚举

题意

二维平面里面，有 \(n\) 个人，\(m\) 个灯塔。灯塔 \((c_i,d_i)\) 照亮的范围是 $(x, y) $ 如果 \(x \le c_i\) 且 \(y \le d_i\) . 所有人必须一起移动，它们在一步内可以左右或者上下移动。求最小的步数，使得所有人远离灯塔的范围。

分析

如果把题目抽象一下。\((a_i,b_i)\) 和 \((c_i,d_i)\) 是人和灯塔。那么要求一个 \((x,y)\) 使得对于所有人来说都不被所有灯塔照亮。也就是对于每个人和每个灯塔 \(a_i+x > c_j\) 或者 \(b_i +y > c_j\) 至少一个成立。那么我们枚举 \((i,j)\) ，把所有的对都枚举出来，并且只留下不满足的二元对。然后把这些对按 \(x\) 排序。那么我们可以枚举 \(x\) , 假设我们向上移动 \(x\), 那么 \(y\) 就是所有比 \(x\) 大的对中的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m;
int a[maxn], b[maxn],c[maxn], d[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n; ++i) {
        cin >> a[i] >> b[i];
    }   
    for (int i = 1;i <= m; ++i) {
        cin >> c[i] >> d[i];
    }
    vector<pii> A;
    for (int i = 1;i <= n; ++i) {
        for (int j = 1;j <= m; ++j) {
            if (c[j] - a[i] >= 0 && d[j] - b[i] >= 0 )
                A.push_back({c[j] + 1 - a[i], d[j] + 1 - b[i]});
        }
    }
    sort(A.begin(), A.end());
    ll mx = 0;
    ll ans = 1e18;
    for (int i = sz(A)-1; i >= 0; --i) {
        auto [x, y] = A[i];  
        ll cur = x + mx;
        ans = min(ans, cur);  
        mx = max(mx, (ll)y);
    }
    ans = min(ans, mx);
    if (ans > 1e9) cout << 0 << endl;
    else cout << ans << endl;
    return 0;
}

Maximum Subsequence Value

枚举+二分

1413C Perform Easily

题意

分析

因为音符的顺序和琴弦的顺序没有影响，所以我们把音符和弦排序。枚举一个位置 \(minx\) 作为最右边的音符。那么其他的音符摆放的位置要不浪费。不浪费也就是说，尽可能往右边摆放。那么一个音符如果往下挪一行就越过最右边了，那么它就应该摆在上一行。应该是摆在这一行刚好在 \(minx\) 左边一点。那么这个值必定是印象最大值的。因为根据排序，之前枚举的值肯定比当前的值小，那么它摆在同一行的上面肯定在当前的值的右边。所以我们对于每个琴弦，二分查找一下刚好不去下一行中最大的那个音符 \(B_i\)。若这一行琴弦的值是 \(a_j\) 那么就是 \(B_i-a_j <= minx\) 且 $B_i-a_{j+1} > minx $ 也就是 \(minx + a_{j+1}\) 的前驱。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}

int n, m;
int A[7], B[maxn];
vector<int> a;

int solve(int minx) {
    vector<pair<int, int>> lr; 
    int cur = 0;
    for (int k = 1;k < sz(a); ++k){
        int pos = lower_bound(B+1, B+n+1, minx + a[k]) - B - 1; // 前驱
        cur = max(cur, B[pos] - a[k-1]);
    }
    for (int k = sz(a)-1;k >= 0; --k) {
        if (B[n] - a[k] >= minx) {
            cur = max(cur, B[n] - a[k]);
            break;
        }
    }
    return cur;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 1;i <= 6; ++i) {
        cin >> A[i];
    }
    sort(A+1, A+6+1);
    for (int i = 1;i <= 6; ++i) {
        if (a.empty() || A[i] != a.back()) a.push_back(A[i]);
    }
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        cin >> B[i];
    }
    sort(B+1, B+n+1);
    int ans = INT_MAX;
    for (int i = 0;i < sz(a); ++i) {
        for (int j = 1;j <= n; ++j) {
            int minx = B[j] - a[i];
            if (B[1] - a[0] < minx) continue;
            int cur = solve(minx);
            ans = min(cur - minx, ans);
        }
    }
    cout << ans << endl;
    return 0;
}