Codeforces Round 965 (Div. 2)解题（C）

Codeforces Round 965 (Div. 2)解题（C）

场次链接：https://codeforces.com/contest/1998

C. Perform Operations to Maximize Score

题目：

解题思路：
最终答案为 $a_i+\mathrm{median}(c_i)$ 的最大值， 显然当$a_i$取最大值时，我们可以使得所取的$a_i+\mathrm{median}(c_i)$ 最大， 然后我们还可以进行k次操作，那么我们只有两种情况更新答案，一种是更新$a_i$；另一种是更新 $median(c_i)$ ，我们只需要比较两种情况中的最大值就行了

复盘：
自己写的时候思路没有捋清楚，没有分两次考虑，一次只更新其中一种，然后比较两种情况的最大值，而是一次循环把两种情况都考虑了，用k又是看看能不能更新最大值，又是看看能不能更新mid值，然后进行比较，虽然可能也可以直接一次性搞定，但很显然，对我而言难度太大了，一直WA，最后时间结束了也没有调出来，而且我还没有用pair，而是用abc三个数组，c是a排完序后的数组，这样导致光是判断当前的a[i]的b是否为1就非常困难了，进一步加大了思维难度

反思：

1. 对两个序列相互联系的情况，可以考虑用pair
2. 找到答案中的重点，然后进行分解，看能不能一次只考虑其中的一个，分多次考虑，以此减低思维难度，例如此题，显然答案重点一个是$a_i$, 一个是$median(c_i)$，就可以分两次分别考虑更新其中一个，最后比较最大值就行了

代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl '\n'
#define pii pair<int, int>

const ll MOD = 1e9+7;
const ll INF = 1e18;
const int MAXN = 2e5+9;

void solve() {
    ll n, k; cin >> n >> k;
    vector<pii> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].first;
    for (int i = 0; i < n; i++) cin >> a[i].second;
    sort(a.begin(), a.end());

    ll ans = 0;
    //更新a[i]的最大值，如果a[i]+k大于原最大值，则更新
    for (int i = 0; i < n; i++) {
        if (a[i].second == 1) {
            int med;
            if (i < n/2) med = a[n/2].first;
            else med = a[n/2-1].first;
            ans = __max(ans, 0LL + a[i].first + k + med);
        }
    }
    //二分遍历范围a[i]的范围，找到有k次操作时med的最大值
    int lo = 0, hi = 2e9;
    while (lo != hi) {
        int mid = (1LL + lo + hi) / 2;
        int z = 0; //记录大于当前mid的a[i]个数
        vector<int> smaller_list;
        for (int i = 0; i < n-1; i++) {
            if (a[i].first >= mid)
                z++;
            else if (a[i].second == 1) //如果b[i]==1，则可能通过k操作使得当前a[i]>mid
                smaller_list.push_back(mid - a[i].first); //记录当前a[i]与mid的差值，之后可以用k来补
        }
        //因为是递增排序，逆序操作，变递减排序，使得通过k操作后a[i]>mid的值尽可能多
        reverse(smaller_list.begin(), smaller_list.end());
        //有多重循环，当前循环用kk暂代k
        int kk = k;
        for (auto x : smaller_list) {
            if (kk >= x) { //所剩的k操作次数可以补
                kk -= x;
                z++;
            }
        }
        //通过z更新二分范围
        //大于当前mid的值大于等于a[i]个数的一半，说明当前mid<=所求mid, 更新lo
        if (z >= (n+1)/2) lo = mid;
        //否则，更新hi
        else hi = mid-1;
    }
    ans = __max(ans, 0LL + a[n-1].first + lo); //与上一种情况进行比较

    cout << ans << nl;
}


int main () {
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}
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
63
64
65
66
67
68
69
70
71
72
73