hihocoder-1384 Genius ACM

Time Limit: 3000ms
Memory Limit: 256MB

Description

Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturer in the world. Every day, they manufacture n CPU chips and sell them all over the world.

As you may know, each batch of CPU chips must pass a quality test by the QC department before they can be sold. The testing procedure is as follows:

1) Randomly pick m pairs of CPU chips from the batch of chips (If there are less than 2m CPU chips in the batch of chips, pick as many pairs as possible.)

2) For each pair, measure the Relative Performance Difference (RPD) between the two CPU chips. Let Di be the RPD of the i-th pair

3) Calculate the Sqared Performance Difference (SPD) of the batch according to the following formula:

SPD=∑Di2

If there are only 1 CPU in a batch, then the SPD of that batch is 0.

4) The batch of chips pass the test if and only if SPD≤k, where k is a preseted constant

Usually they send all the n CPU chips as a single batch to the QC department every day. As one of the best CPU manufacturer in the world, ACM never fail the test. However, with the continuous improvement of CPU performance, they find that they are at risk!

Of course they don’t want to take any risks. So they make a decision to divide the n chips into several batches to ensure all of them pass the test. What’s more, each batch should be a continuous subsequence of their productions, otherwise the QC department will notice that they are cheating. Quality tests need time and money, so they want to minimize the number of batches.

Given the absolute performance of the n chips P1 … Pn mesured by ACM in order of manufacture, your task is to determine the minimum number of batches to ensure that all chips pass the test. The RPD of two CPU chips equals to the difference of their absolute performance.

Input

The first line contains a single integer T, indicating the number of test cases.

In each test case, the first line contains three integers n, m, k. The second line contains n integers, P1 … Pn.

$T≤12$

$1 \leq n,m \leq 5×10^5$

$0≤k≤10^{18}$

$0≤Pi≤2^{20}$

Output

For each test case, print the answer in a single line.

Smaple Input

样例输出

2
1

解题思路

对于一个集合 $S$，要使 $SPD$ 最大，显然是先排序，将最大的数和最小的数组队。那么问题就转化为在数组中对于已知的左边界 $i$，右端点在满足 $SPD$ 限制条件下，最大可以取到什么值。

我们可以采用倍增的方式
– 初始化 $p=1$，$R=L$
– 求出 $[L,R+p]$ 的 $SPD$，如果小于 $k$，则$R+=p$，$p *= 2 $，否则 $ p /= 2 $

但是这样依旧会TLE，我们可以优化求每段区间$SPD$的方式，不用每次都全部排序，而是之将新增长度为 $p$ 部分排序，采用类似归并排序的方式并入符合条件的已排序数组中。

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int MAXN = 5000000 + 10;

long long data[MAXN];
long long tmp[MAXN];
long long tmp2[MAXN];
long long tmp3[MAXN];
long long tmp4[MAXN];

long long n, m, q, T, cnt;

inline long long read(){
    long long x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

inline long long calc(int l, int r, int R){
    for(register int i=l ;i <= r; i++){
        tmp2[i] = tmp[i];
    }
    for(register int i=r+1; i<=R; i++){
        tmp3[i] = data[i];
    }
    sort(tmp3+r+1, tmp3+R+1);

    int i=l, j = r + 1;

    for(register int k=l; k<=R; k++){
        if(j > R || i <= r && tmp2[i] < tmp3[j])
            tmp4[k] = tmp2[i++];
        else
            tmp4[k] = tmp3[j++];
    }

    long long ans = 0;
    int x = 0;

    while(R - l >= 1 && ++x <= m){
        ans += pow(tmp4[R--] - tmp4[l++], 2);
    }

    return ans;
}

inline int work(int l){
    int p = 1;
    int r = l;

    tmp[l] = data[l];

    while(p && r <= n){
        if(calc(l, r, r + p) <= q){
            r += p;
            p <<= 1;

            for(register int i=l; i<=r; i++)
                tmp[i] = tmp4[i];

        }else{
            p >>= 1;
        }
    }

    cnt++;
    return r;
}

int main(){
    T = read();

    while(T--){
        cnt = 0;

        n = read();
        m = read();
        q = read();

        for(register int i=1; i<=n; i++)
            data[i] = read();

        int l = 1;
        while(l <= n){
            l = work(l) + 1;
        }

        printf("%dn", cnt);

    }
    return 0;
}

[题解] hihocoder-1384 Genius ACM

BLOG