251208 以前 x 天

CF335F Buy One, Get One Free

考虑贪心，每次加入一段值相等的数，如果还有免费额度就先用免费额度，否则尝试拆掉原来的匹配并新生成两个免费额度。如果被拆除的匹配 \(i\to j\) 就是拆除 \(j\) 的匹配而获得的，那么复原 \(j\) 的匹配可能更优，这里需要处理。

代码

#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int N = 5e5 + 10;

int n, ans;
int a[N];
int sta[N], top;

priority_queue<int, vector<int>, greater<int>> que;

signed main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    sort(a + 1, a + 1 + n);
    for(int i = n, cnt; i >= 1; i -= cnt) {
        cnt = 1;
        for(int j = i - 1; j >= 1 && a[j] == a[i]; j--) ++cnt;
        int t = n - i - que.size() * 2;
        for(int j = 1; j <= min(cnt, t); j++) sta[++top] = a[i];
        if(cnt > t) {
            int r = cnt - t;
            while(!que.empty() && que.top() < 2 * a[i] && r >= 2) {
                ans += que.top();
                if(que.top() >= a[i]) {
                    sta[++top] = 2 * a[i] - que.top();
                    sta[++top] = que.top();
                } else {
                    sta[++top] = a[i], sta[++top] = a[i];
                }
                r -= 2;
                que.pop();
            }
            if(r && !que.empty() && que.top() < a[i]) {
                ans += que.top(); que.pop();
                sta[++top] = a[i];
                r--;
            }
            ans += r * a[i];
        }
        while(top) que.push(sta[top--]);
    }

    cout << ans << '\n';

    return 0;
}

CF1733E Conveyor

将问题转化为前 \(t\) 秒 \((x,y)\) 经过了多少货物。发现 \((x,y)\) 有恰好一半转移到右边，恰好一半转移到下面，因此可以 \(O(n^2)\) 求出答案。

AT_acl1_f Center Rearranging

枚举哪个区间的数字是没有动过的，之后对所有数组分讨 9 种情况，最后一种用 2-SAT 解决即可。

CF1768F Wonderful Jump

如果一次跳跃的两个端点 \(i\to j\) 满足 \([i,j]\) 的最小值不在端点处，那么可以先跳到最小值，代价变小。因此 \(i,j\) 中至少一个是区间最小值。

对于一个区间，考虑一种最朴素的策略：一步一步跳过去，总代价不超过 \(n\times d\)（\(d=j-i\)）；而一次跳过去，代价为 \(a_i\times d^2\)。因此跳一次需要满足 \(a_i\times d^2\le nd\)，即 \(d\le\frac{n}{a_i}\)。对 \(a_i\) 根号分治，如果 \(a_i\ge \sqrt n\)，那么直接暴力转移；否则以 \(a_i\)（值）同时为区间最小值和左端点的区间总数是 \(O(n)\) 级别的，而 \(a_i\) 也只有 \(\sqrt n\) 种，因此时间复杂度是对的。

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

强制在线，区间众数。