新知识:倍增
目前为止遇到的题目中,这题的难度能进前三
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 500010; 5 int n, m; //n是长度,m是对数 6 ll T; //T是最大值 7 ll w[N], tmp[N], t[N]; 8 //w是输入的数组 9 //tmp是用于归并排序的数组 10 //t是用于求校验值的数组 11 ll sq(ll x) { 12 return x * x; 13 } 14 bool check(int l, int mid, int r) { 15 //判断区间[l, r)是否合法,并将t中的[l, mid)区间和[mid, r)区间合并到 tmp 中 16 for (int i = mid; i < r; i++) { 17 //将w数组的[l, r)区间复制到t的[l, r)区间中 18 t[i] = w[i]; 19 } 20 sort(t + mid, t + r); //t的[mid, r)排序 21 int i = l, j = mid, k = 0; //双指针进行区间合并 22 while (i != mid && j != r) { 23 if (t[i] <= t[j]) { 24 tmp[k++] = t[i++]; 25 } else { 26 tmp[k++] = t[j++]; 27 } 28 } 29 while (i != mid) { 30 tmp[k++] = t[i++]; 31 } 32 while (j != r) { 33 tmp[k++] = t[j++]; 34 } 35 ll sum = 0; // 计算校验值 36 for (i = 0; i < m && i < k; i++, k--) { 37 sum += sq(tmp[i] - tmp[k - 1]); 38 } 39 return sum <= T; //返回当前区间[l, r)是否合法 40 } 41 int main() { 42 int K; 43 cin >> K; 44 while (K--) { 45 cin >> n >> m >> T; 46 for (int i = 0; i < n; i++) { 47 cin >> w[i]; 48 } 49 int ans = 0; //答案,划分的最大段数 50 int st = 0, ed = 0; 51 //st记录剩余区间开头节点,end记录当前考虑区间的尾结点(左闭右开) 52 while (ed < n) { //只要没走完 53 int len = 1; //每一次的步长 54 while (len) { //只要步长不为0 55 if (ed + len <= n && check(st, ed, ed + len)) { 56 //如果说len+end还在n以内,且区间[st,ed+len)的校验值不大于T 57 ed += len; 58 len *= 2; 59 if (ed >= n) { 60 break ; //一个小剪枝,如果ed>=n,那么直接跳出 61 } 62 for (int i = st; i < ed; i++) { 63 //在check时,已经将t数组的[st,ed + len)这段区间归并在tmp中了 64 //现在只需要将tmp中的有序数组复制到t中即可 65 t[i] = tmp[i - st]; 66 //复制的时候注意下标变换 67 //tmp是从0开始存的,t是从st开始存的 68 } 69 } else { 70 len /= 2; 71 } 72 } 73 st = ed; //让start指向当前区间末尾结点的下一个位置,由于区间是左闭右开的,所以直接指向end就可以了 74 ans++; //每次循环都找到了一个区间,所以让ans++ 75 } 76 cout << ans << endl; 77 } 78 return 0; 79 }