109. 天才ACM
给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:
从集合 S中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 S的“校验值”。 现在给定一个长度为 N的数列 A 以及一个整数 T。 我们要把 A分成若干段，使得每一段的“校验值”都不超过 T。 求最少需要分成几段。输入格式
第一行输入整数 K，代表有 K组测试数据。 对于每组测试数据，第一行包含三个整数 N,M,T。 第二行包含 N个整数，表示数列A1,A2…AN。输出格式
对于每组测试数据，输出其答案，每个答案占一行。数据范围
1≤K≤12, 1≤N,M≤500000, 0≤T≤1018, 0≤Ai≤220输入样例：
2 5 1 49 8 2 1 7 9 5 1 64 8 2 1 7 9输出样例：
2 1#include#include #include #define ll long long using namespace std;const int N = 500010;int n, m, mid;ll k, a[N], b[N], c[N];void merge(int l, int mid, int r){ //if(r == n) break; int i = l, j = mid + 1; for(int k = l; k <= r; k++) // k = L if(j > r || (i <= mid && b[i] <= b[j])) c[k] = b[i++]; else c[k] = b[j++]; //赋值回数组b在下面} ll f(int l, int r) //求校验值 贪心取集合s中最大的M个数和最小的M个数，最大和最小配成一对...{ if(r > n) r = n; int small = min(m, (r - l + 1) >> 1);//求最小值，长度（r - l + 1）/ 2 for(int i = mid + 1; i <= r; i++) b[i] = a[i]; //mid + 1 = 2 从2开始幅值，所以前面b[1] = a[1] sort(b + mid + 1, b + r + 1); merge(l, mid, r); ll ans = 0; //至少分几段 for(int i = 0; i < small; i++) ans += (c[r-i] - c[l+i]) * (c[r-i] - c[l+i]); //每对数的差的平方之和 return ans;}void Genius_ACM(){ cin >> n >> m >> k; for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); int ans = 0, l = 1, r = 1; mid = 1; b[1] = a[1]; while(l <= n) { int p = 1; //初始化步长p = 1 while(p) { ll num = f(l, r + p); // 求校验值num if(num <= k) //不超过整数k { mid = r = min(r + p, n); for(int i = l; i <= r; i++) b[i] = c[i]; //int i = l 是L if(r == n) break; p <<= 1; // p = p * 2 } else p >>= 1; } ans ++; l = r + 1; } cout << ans << endl;}int main(){ int t; cin >> t; while(t--) Genius_ACM(); return 0;}