算法竞赛进阶指南-0x06基本算法-倍增

天才ACM

题意：
蓝书P40

Solution：
很详细的题解

Code:

int Te, n, m;
ll a[N], t[N], tmp[N], T;

bool check(int l, int mid, int r){
    for(int i = mid; i < r; i ++)   t[i] = a[i];
    sort(t + mid, t + r);
    int i = l, j = mid, k = 0;
    while(i < mid && j < r){
        if(t[i] < t[j])
            tmp[k ++] = t[i ++];
        else
            tmp[k ++] = t[j ++];
    }
    while(i < mid) tmp[k ++] = t[i ++];
    while(j < r)   tmp[k ++] = t[j ++];
    ll cnt = 0;
    for(int i = 0; i < m && i < k; i ++,  k --){
        cnt += (tmp[i] - tmp[k - 1]) * (tmp[i] - tmp[k - 1]);
    }
    return cnt <= T;
}

int main(){
    __;
    cin >> Te;
    while(Te --){
        cin >> n >> m >> T;
        int ans = 0;
        for(int i = 0; i < n; i ++)    cin >> a[i];
        int len;
        int st = 0, ed = 0;
        while(ed < n){
            len = 1;
            while(len){
                if(ed + len <= n && check(st, ed, ed + len)){
                    ed += len;
                    len <<= 1;
                    if(ed >= n)  break;
                    for(int i = st; i < ed; i ++){
                        t[i] = tmp[i - st];
                    }
                }
                else{
                    len >>= 1;
                }
            }
            st = ed;
            ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

ST表