笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 CF958E2 【Guard Duty (medium)】

posted on 2020-03-28 14:28:02 | under 题解 |

另一个老哥是真莽,$nk=5\cdot 10^5*5\cdot 10^3=2.5e9$ 这都能 2995ms 给爆过去,orzorz

发现题解区好像没有正常复杂度的,于是这里给出一个正常一点的带权二分做法。


考虑一般 $dp$ 的话就是 $f_{i,j}$ ,这个地方由于不限制一定要取满,所以就可以有如下转移:$$ f_{i,j}=\min\{f_{i-1,j},f_{i-2,j-1}+len(i-1,i)\} $$ 似乎常数小一点,暴力 $O(nk)$ 也是可以过的。于是就直接wqs二分一下,注意到由于此时最优的决策一定是少选,所以每选一次就需要减去 $mid$ 来维护这个限制。于是最后复杂度 $n\log V$ 。

需要注意的是,由于用了 $cnt_i$ 记录转移到 $i$ 这个状态至少要分成多少段,所以这个地方还是牵扯到一个,如果我可以有 $6/7/8$ 三种划分方式转移到最优解,那么到底应该用哪个。很显然的是要么用 $max$ 要么用 $min$,这取决于二分的方式。如果是取 $max$ 的话,那么可能 $cnt_n>m$ ;取 $min$ 的话则会 $\leq m$ 。所以根据这个调整代码细节就好了。

ll res ;
ll f[N] ;
int m, n ;
int df[N] ;
int cnt[N] ;
int base[N] ;

bool check(int x){
    x *= -1 ;
    for (int i = 2 ; i <= n ; ++ i){
        if (f[i - 1] < f[i - 2] + df[i] + x)
            f[i] = f[i - 1], cnt[i] = cnt[i - 1] ; 
        else f[i] = f[i - 2] + (ll)df[i] + (ll)x, cnt[i] = cnt[i - 2] + 1 ;
        if (f[i - 1] == f[i - 2] + df[i] + x) cnt[i] = max(cnt[i - 1], cnt[i - 2] + 1) ;
    }
    res = f[n] - (ll)x * m ; return (bool)(cnt[n] >= m) ;
}
int main(){
    cin >> m >> n ; 
    for (int i = 1 ; i <= n ; ++ i) 
        scanf("%d", &base[i]) ; 
    sort(base + 1, base + n + 1) ; 
    for (int i = 1 ; i <= n ; ++ i) 
        df[i] = base[i] - base[i - 1] ;
    int l = 0, r = 1e9, mid, ans ; 
    while (l <= r){
        mid = (l + r) >> 1 ; 
//      cout << l << " " << r << endl ; 
        if (check(mid)) ans = mid, r = mid - 1 ;
        else l = mid + 1 ;
    }   
    check(ans) ; cout << res << endl ; return 0 ;
}