[BZOJ P2771] 天才ACM
朴素算法
枚举终点 \(r\),对区间 \([l, r]\) 排序求校验值 \(sum\),比较 \(sum\) 和 \(t\)
- $ sum \le t $
r++
- $ sum > t $
l=++r,ans++
时间复杂度N2log N
初步优化
考虑校验值单调不下降,可枚举左端点l时二分右端点r,再对区间l~r求校验值,更新方法如上
时间复杂度 \(O(N\log^2N)\)
但是我们会发现这道题还是过不去,于是仔细读题,发现有一个很恶心的K组数据,那么就需要进一步卡常优化
卡常 最后优化
可以发现,当我们二分右端点r时计算校验值会重复排序已排序的部分,考虑不去重复计算
- 使用归并的思想对满足条件的部分和待排序的部分合并,常数优化
- 前一步的基础是区间长度单调不减,所以考虑使用倍增思想增加长度,定义一个变量
p
,每次判断l~r+p是否满足校验值不大于T- 满足
r+=p,p<<=1;
- 不满足
p>>=1
- p==0
ans++,r++,l=r,p=1;
- 满足
最后
总结一下,这道题是一道抽象的倍增和二分,思维难度较高但知识难度不是很高的好题,稍微需要一点卡常优化技巧
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
int t, n, m, ans;
LL s, sum;
LL a[N], f[N], mg[N];
inline void merge(int l, int r, int mid) {
int i = l, j = mid + 1;
for (int k = l;k <= r;k++)
if (j > r || i <= mid && f[i] <= f[j]) mg[k] = f[i++];
else mg[k] = f[j++];
}
inline bool check(int l, int r, int mid) {
for (int i = mid;i <= r;i++) f[i] = a[i];
sort(f + mid, f + r + 1);
merge(l, r, mid - 1);
sum = 0;
for (int i = 1;i <= ((r - l + 1) >> 1) && i <= m;i++) sum += (mg[r - i + 1] - mg[l + i - 1]) * (mg[r - i + 1] - mg[l + i - 1]);
if (sum <= s) {
for (int i = l;i <= r;i++) f[i] = mg[i];
return true;
}
else return false;
}
int main() {
scanf("%d", &t);
while (t--) {
ans = 0;
scanf("%d%d%lld", &n, &m, &s);
for (int i = 1;i <= n;i++) scanf("%lld", &a[i]);
int l = 1, r = 1, p = 1;
f[1] = a[1];
while (r <= n) {
if (p == 0) {
ans++, r++;
l = r, f[l] = a[l], p = 1;
}
else if (r + p <= n && check(l, r + p, r + 1)) r += p, p <<= 1;
else p >>= 1;
}
printf("%d\n", ans);
}
return 0;
}
标签:int,sum,校验,ACM,++,ans,P2771,排序,BZOJ
From: https://www.cnblogs.com/keysky/p/18678626