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

mm 升序排序

fi,jf_{i, j}1i1\sim i 个人投,并且 i+1ni+1\sim n 中有 jj 个人在前 ii 个人之前投

fi,j=min{fi1,j+1+pifi1,j    if  i1+jmi 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

mm 降序考虑

考虑所有 mi=xm_i=x ,记 mi=xm_i=x 的人数为 ss,记 mi<xm_i<x 的人数为 pp

pxp\ge x 可以直接继续考虑

p<xp < x 则需要在 mi>xm_i>x 中买人,用 multiset 维护一下

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

设当前正在考虑 mi=xm_i = xmi=xm_i=x 的人数为 ssmi<xm_i<x 的人数为 pp

第一个 mi>xm_i>x,记 y=miy=m_i,必然有 p+s+cntyp+s+cnt\ge y

考虑 xxneed=xpcntneed = x-p-cnt

sneed=sx+p+cnt=yx>0s-need=s-x+p+cnt=y-x>0

所以 s>needs>need

所以不用考虑买全部 mi=xm_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;
}