【例题】CH0601 Genius ACM

80分写法：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn=500000+10;
 6 int n, m, p, q, a[maxn], b[maxn];
 7 long long t;
 8 
 9 long long check(int l, int r) {
10     int tot=0;
11     for (int i=l; i<=r; ++i)
12         b[++tot]=a[i];
13     sort(b+1, b+tot+1);
14     long long sum=0;
15     int len=r-l+1;
16     if (len>=m*2) {
17         for (int i=1; i<=m; ++i)
18             sum+=(b[len-i+1]-b[i])*(b[len-i+1]-b[i]);
19     }
20     else {
21         for (int i=1; i<=len/2; ++i)
22             sum+=(b[len-i+1]-b[i])*(b[len-i+1]-b[i]);
23     } 
24     return sum;
25 }
26 
27 int batch(int l) {
28     int p=1, r=l;
29     while (p>0) {
30         if (p) {
31             if (r+p<=n && check(l, r+p)<=t) {
32                 r+=p; p*=2;
33             }
34             else {
35                 p/=2;
36             }
37         }
38         //printf("%d %d %lld\n", p, r, check(l, r));
39     }
40     return r+1;
41 }
42 
43 int main() {
44     int T;
45     scanf("%d", &T);
46     while (T--) {
47         scanf("%d%d%d", &n, &m, &t);
48         for (int i=1; i<=n; ++i)
49             scanf("%d", &a[i]);
50         int ans=0;
51         for (int i=1; i<=n; i=batch(i), ans++);
52         printf("%d\n", ans);
53     } 
54     return 0;
55 } 
56 /*
57 1
58 10 4 20
59 1 5 2 3 6 2 5 4 2 3
60 */

ST算法

 

void ST_prework() {
    for (int i=1; i<=n; ++i)
        f[i][0]=a[i];
    int t=log(n)/log(2)+1;
    for (int j=1; j<t; ++j)
        for (int i=1; i<=n-(1<<j)+1; ++i)
            f[i][j]=max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}

void ST_query(int l, int r) {
    int k=log(r-l+1)/log(2)+1;
    return max(f[l][k], f[r-(1<<k)+1][k]);
}