天才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;
}