Codeforces Round 892 (Div. 2)

wuyoudexian / 2023-08-13 / 原文

手速慢了，掉分

C. Another Permutation Problem

Problem - C - Codeforces

题意

给定一个正整数\(n\)，设序列\(p\)为\(n\)的排列，求\(\sum_{i=1}^{n}p_i \times i-max_{j=1}^np_j\times j\)的最大值。

思路

打表可知，答案的排列一定为翻转一部分后缀。暴力枚举要翻转的后缀即可。

代码

void solve() {
    int n;
    cin >> n;

    int ans = 0;
    for(int i = 1; i < n; i++) {
        ans += i * i;
    }

    for(int i = 0; i < n; i++) {
        int x = 0, y = 0, mx = 0;
        for(int j = 1; j <= i; j++) {
            x += j * j;
            mx = max(mx, j * j);
        }
        
        for(int j = n, k = i + 1; j > i; j--, k++) {
            y += k * j;
            mx = max(mx, k * j);
        }

        ans = max(ans, x + y - mx);
    }

    cout << ans << "\n";
}

D. Andrey and Escape from Capygrad

Problem - D - Codeforces

题意

给定一些包含区间，\([l, r]\)包含区间\([a,b]\)，如果一个人在区间\([l,r]\)内，那么他可以传送到区间\([a,b]\)中的任意点。现给定一些坐标，求从该总表出发，最大能传送到的坐标在哪里。

思路

题意可简化为有若干个区间\([l,b]\)，在区间\([l,b]\)内可传送到端点\(b\)，求最大能传送到的坐标。

先合并重合的区间，再对于每个询问的坐标，二分找到所在的区间。若该坐标不在任何区间，则答案为它自已。

代码

void solve() {
    int n;
    cin >> n;
 
    vector<array<int, 2>> seg(n);
    for(int i = 0; i < n; i++) {
        int l, r, a, b;
        cin >> l >> r >> a >> b;
        seg[i] = {l, b};
    }
 
    sort(seg.begin(), seg.end());
 
    vector<array<int, 2>> a;
    for(int i = 0; i < n; i++) {
        if(!a.empty() && a.back()[1] >= seg[i][0]) {
            a.back()[1] = max(a.back()[1], seg[i][1]);
        } else {
            a.push_back({seg[i][0], seg[i][1]});
        }
    }
 
    int q;
    cin >> q;
 
    while(q--) {
        int x;
        cin >> x;
 
        int p = lower_bound(a.begin(), a.end(), array{x + 1, 1}) - a.begin() - 1;
        if(p >= 0) {
            x = max(x, a[p][1]);
        }
        cout << x << " ";
    }
 
    cout << "\n";
}