Codeforces 1355E

Chong Wang Lv6
  2020-05-17 10:45:54 2020-05-17 10:45:54 Created   2026-10-09 08:40:46 2026-10-09 08:40:46 Updated  

This is a textbook ternary-search problem: find an extremum over an interval.

What on earth was I doing, though? I finally got it accepted in the last minute. I am back to the purple rating again. I want to reach 2100 this year; if I can become consistent, it is not impossible.

lastMinute

Codeforces really rewards boldness: dare to think, do, and try. For Problem D, I submitted an approach I barely understood and it passed. I expected to finish with two problems at my level, but I solved three in the final hour.

I also wrote a pseudo-algorithm version and it passed. Analyse the possible exchanges: only three target values need consideration—sum / n, and, when the remainder is non-zero, two neighbouring values.

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
ll n,a,r,m;
ll val[maxn];
ll pre[maxn], t1[maxn],t2[maxn];
void solve() {
    SLLA(n);
    SLLA(a);
    SLLA(r);
    SLLA(m);
    REPP(i,1,n) {
        SLLA(val[i]);
        t1[i] = val[i];
        t2[i] = val[i];
    }
    sort(val+1,val+1+n);
    sort(t1+1,t1+1+n);
    sort(t2+1,t2+1+n);
    REPP(i,1,n) {
        pre[i] = pre[i-1] + val[i];
    }
 
    ll A = a;
    ll R = r;
    ll ans = LL_INF;
    REPP(i,1,n) {
        ll fix = val[i];
 
        ll p = pre[i-1];
        ll need = (i-1)*fix - p;
 
        ll suf = pre[n] - pre[i];
        ll nedre = suf - (n-i) * fix;
 
        ll tmp = need*A + nedre*R;
        ans = min(ans, tmp);
 
        ll cnt = min(need, nedre);
        
        need -= cnt;
        nedre -= cnt;
        tmp = cnt*m + need*A + nedre*R;
        ans = min(ans, tmp);
    }
    if(pre[n] % n == 0) {
        ll s = 0;
        REPP(i,1,n) {
            s += abs(pre[n]/n - val[i]);
        }
        ans = min(ans, s/2*m);
    } else {
       ll sur = pre[n]%n;
       ll anst1 = sur*R;
       ll cn = sur;
       ll ind = n;
              ll sum = pre[n];
       sum -= sur;
       while(cn>=1) {
        while(cn>=1 && t1[ind] > sum/n) {
            t1[ind]--;
            cn--;
        }
        ind--;
       }
 
       ll tmp = 0;
       REPP(i,1,n) {
            tmp += abs(sum/n - t1[i]);
       }
       ans = min(ans, tmp/2*m+anst1);

       ll sur_sum = n - pre[n]%n;
       sum = pre[n] + sur_sum;
       int cntt = 0;
       int i = 1;
       while(cntt < sur_sum) {
        while(t2[i] < sum/n && cntt < sur_sum) {
            cntt++;
            t2[i]++;
        }
        i++;
       }
       ll anst2 = sur_sum*A;
       tmp = 0;
       REPP(i,1,n) {
            tmp += abs(sum/n - t2[i]);
       }
       ans = min(ans, tmp/2*m + anst2);
    }
    printf("%lld\n", ans);
}

The ternary-search solution below is adapted from quality:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
int h[MAXN];
int main()
{
    int n,A,R,M;
    scanf("%d%d%d%d",&n,&A,&R,&M);
    M=min(M,A+R);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    auto f=[&](int t)->ll
    {
        ll cnt_a=0,cnt_r=0;
        for(int i=1;i<=n;i++)
        {
            if(h[i]<t)cnt_a+=t-h[i];
            else cnt_r+=h[i]-t;
        }
        ll cnt_m=min(cnt_a,cnt_r);
        cnt_a-=cnt_m,cnt_r-=cnt_m;
        return A*cnt_a+R*cnt_r+M*cnt_m;
    };
    int tl=0,tr=1000000000;
    while(tl<tr)
    {
        int tm1=tl+(tr-tl)/3;
        int tm2=tl+(2*tr-2*tl+2)/3;
        if(f(tm1)>f(tm2))tl=tm1+1;
        else tr=tm2-1;
    }
    return 0*printf("%lld\n",f(tl));
}
On this page
Codeforces 1355E