[Hihocoder1384] Genius ACM(倍增，贪心)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：http://hihocoder.com/problemset/problem/1384

n个数分成至少多少段，使得每段中最大和最小的m对数之差不大于k？

这是一道很nice的题目，来自《算法竞赛进阶指南》P38.

考虑区间长度L，当然希望L越大越好，因为每段中最大和最小的m对数之差随着L递增，因此可以这样贪心。

于是倍增L，每次暴力check区间是否满足条件，复杂度是$Nlog^2N$，成功被卡。

考虑区间[l, r]和(r, r+p]的关系，我们每次必然会给(r, r+p]排序，但是[l, r]没有影响，只是最后判断[l, r+p]是否满足会影响到区间的长度，一旦判断可以继续扩大那么这个区间就不会再动了，因此这段区间是可以有序的。因此拆成[l, r]和(r, r+p]两段，每次对(r, r+p]排序，判断ok再与之前的区间merge即可。 

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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 500500;
int n, m;
LL k, a[maxn], b[maxn], c[maxn];

bool ok(int l, int r) {
  LL ret = 0;
  int cnt = 0;
  for (int i = l, j = r; i < j && cnt < m; i++, j--, cnt++) {
    ret += (c[j] - c[i]) * (c[j] - c[i]);
    if (ret > k) {
      return 0;
    }
  }
  return 1;
}

inline bool scan_d(LL &num) {
  char in;bool IsN=false;
  in=getchar();
  if(in==EOF) return false;
  while(in!='-'&&(in<'0'||in>'9')) in=getchar();
  if(in=='-'){ IsN=true;num=0;}
  else num=in-'0';
  while(in=getchar(),in>='0'&&in<='9'){
    num*=10,num+=in-'0';
  }
  if(IsN) num=-num;
  return true;
}

void merge(int l, int r, int mid) {
  int i = l, j = mid;
  for (int k = l; k <= r; k++) {
    if (j > r || (i < mid && b[i] < b[j])) {
      c[k] = b[i++];
    } else {
      c[k] = b[j++];
    }
  }
}

signed main() {
  // freopen("in", "r", stdin);
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %lld", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
      scan_d(a[i]);
    }
    int ret = 0, l = 1;
    while (l <= n) {
      int r = l, p = 1;
      ret++;
      b[l] = a[l];
      while (p) {
        if (r + p > n) {
          p >>= 1;
          continue;
        }
        // a[r+1, r+p]
        for (int i = r + 1; i <= r + p; i++) {
          b[i] = a[i];
        }
        // [l, r]
        // [r+1, r+p]
        sort(b + r + 1, b + r + p + 1);
        merge(l, r + p, r + 1);
        if (!ok(l, r + p)) {
          p >>= 1;
        } else {
          r += p;
          p <<= 1;
          for (int i = l; i <= r; i++) {
            b[i] = c[i];
          }
        }
      }
      l = r + 1;
    }
    printf("%d\n", ret);
  }
  return 0;
}