Educational Codeforces Round 75

又被 God Song 教育了

¶ C

比赛时写了一个假的算法，赛后被教育说直接归并就可以了

char s1[300010], s2[300010], s[300010];
void solve(){
    int pt1 = 0, pt2 = 0;
    cin >> s;
    int n = strlen(s);
    for(int i = 0; i < n; ++i)
        if ((s[i]-'0')&1) s2[pt2++] = s[i];
        else s1[pt1++] = s[i];
    std::merge(s1, s1+pt1, s2, s2+pt2, s);
    cout << s << endl;
}

¶ D

我以为能直接做

结果是个答案二分

没开 ll 全靠 Codeforces 帮我调试

typedef pair<ll, ll> pll;
const int N = 200010;
pll a[N]; int n; ll s;

bool ok(ll mid){
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    ll ans = 0;
    std::vector<ll> v;
    rep(i, 1, n){
        if (a[i].second < mid) ++cnt1, ans += a[i].first;
        else if (a[i].first > mid) ++cnt3, ans += a[i].first;
        else v.push_back(a[i].first);
    }
    if (cnt1 > n/2) return 0;
    int need = std::max(0, n/2+1-cnt3);
    ans += need*mid;
    for(int i = 0; i < v.size() - need; ++i) ans += v[i];
    return ans <= s;
}

void solve(){
    cin >> n >> s;
    ll l = 0, r = s;
    rep(i, 1, n) cin >> a[i].first >> a[i].second;
    std::sort(a+1, a+1+n);

    while(l < r){
        ll mid = (l+r+1)/2;
        if(ok(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

¶ E1

好神的 DP

按 $m$ 升序排序

$f_{i, j}$ 为 $1\sim i$ 个人投，并且 $i+1\sim n$ 中有 $j$ 个人在前 $i$ 个人之前投

$$f_{i,j}=\min\left\{ \begin{aligned} &f_{i-1,j+1} +p_i \\ &f_{i-1,j}~~~~\textbf{if}~~i-1+j\ge m_i \end{aligned} \right.$$

void solve(){
    int n; cin >> n;
    rep(i, 1, n) cin >> a[i].m >> a[i].p;
    std::sort(a+1, a+1+n, cmp);
    rep(i, 1, n){
        rep(j, 0, n){
            f[i][j] = f[i-1][j+1] + a[i].p;
            if (i-1+j >= a[i].m)
                f[i][j] = std::min(f[i][j], f[i-1][j]);
        }
    }
    cout << f[n][0] << endl;
}

¶ E2

按 $m$ 降序考虑

考虑所有 $m_i=x$ ，记 $m_i=x$ 的人数为 $s$，记 $m_i<x$ 的人数为 $p$

若 $p\ge x$ 可以直接继续考虑

若 $p < x$ 则需要在 $m_i>x$ 中买人，用 multiset 维护一下

按道理说应该要特殊考虑把 $m_i=x$ 一起买下来的特殊情况，但是不考虑也是对的 存疑

设当前正在考虑 $m_i = x$ ，$m_i=x$ 的人数为 $s$ ，$m_i<x$ 的人数为 $p$

第一个 $m_i>x$，记 $y=m_i$，必然有 $p+s+cnt\ge y$

考虑 $x$ ， $need = x-p-cnt$

$s-need=s-x+p+cnt=y-x>0$

所以 $s>need$

所以不用考虑买全部 $m_i=x$

std::vector<ll> v[N];

void solve(){
    int n; cin >> n;
    rep(i, 0, n) v[i].clear();
    rep(i, 1, n){
        ll m, p; cin >> m >> p; v[m].push_back(p);
    }
    std::multiset<ll> s;
    ll prev = n, cnt = 0, res = 0;
    per(i, n, 0){
        prev -= v[i].size();
        int need = i - prev - cnt;
        for(auto x : v[i]) s.insert(x);
        for(; need > 0; --need){
            ++cnt;
            res += *s.begin();
            s.erase(s.begin());
        }
    }
    cout << res << endl;
}