前置芝士
求解两个有序数组的第 K 小乘积
先统计分负数乘积个数neg、正数乘积个数pos以及乘积为0的个数 zero，
然后分三种情况讨论：
k≤negk，我们可以二分负数答案，统计不超过二分值的乘积个数；
neg<k≤neg+zero，此时返回0；
k>neg+zero，我们可以二分正数答案，统计不超过二分值的乘积个数。
字段和问题
不限制长度——在一个数列里找两个不相交区间使得他们权值和最大
找 m个长度为 k 的不相交区间使得他们的权值和最大 (1≤n≤5000)
f[i][j]=max(f[i−k][j−1]+sum[i]−sum[i−k],f[i−1][j])
区间数目变多且不限制长度——找 m 个不相交长度不限的区间使得他们权值和最大(1≤n≤5000)
选2个不重叠的长度为k的区间
使子数组和最大
因为区间大小是固定为k的，所以显然需要前缀和处理一下处理之后我们去维护前缀中长度为k的最大值ma，枚举第二个长度为k的起点，那么答案就是max(ma+当前长度为k的序列和)复杂度为O(n).
int T,n,k;
ll a[2000100];
void solve(){
cin>>T;
while(T--){
cin>>n>>k;
for(int i=1;i<=n;i++) {cin>>a[i];a[i]+=a[i-1];}
ll ma=-1e18,ans=-1e18;
for(int i=k;i+k<=n;i++){
ma=max(ma,a[i]-a[i-k]);
ans=max(ans,ma+a[i+k]-a[i]);
}
cout<<ans<<endl;
}
使子数组元素和相等(循环数组)
给你一个下标从 0 开始的整数数组 arr 和一个整数 k ，数组 arr 是一个循环数组，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。
选中 arr 中任意一个元素，并使其值加上 1 或减去 1。
执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。
1 <= k <= arr.length <= 1051 <= arr[i] <= 10^9
【解题思路分析】
1)解决 a不是循环数组的情况
考虑从 i 和 i+1开始的两个长为 k的子数组的和，如果要求这两个和相等，则有
\(a[i]+a[i+1]+⋯+a[i+k−1]=a[i+1]+a[i+2]+⋯+a[i+k]\)
及\(a[i]=a[k+i]=a[2k+i]....\)
2)分组处理
按照 i mod k的结果将 a 分组，对每一组（记作 b）
我们需要解决：
让数组 b的所有元素相等的最少运算次数。
根据中位数贪心，将 b的所有元素变为 b 的中位数是最优的。
3）翡翠定理
比如 n=6,k=4，那么 a[2]循环后是 a[8]，和 a[0]在同一组，而 a[1]无论怎么循环都无法和 a[0] 在同一组。（(1+6n) mod 4≠0
一个循环数组如果既有周期 n，又有周期 k，则必然有周期 gcd(n,k)。证明：根据 裴蜀定理，有：
a[i]=a[i+nx+ky]=a[i+gcd(n,k)]
这样就转换成了不是循环数组的情况。
【java】
public long makeSubKSumEqual(int[] arr, int k) {
int n=arr.length;
k=gcd(n,k);
System.out.println(k);
long res=0;
for(int i=0;i<k;i++){
ArrayList<Integer> list=new ArrayList<>();
for(int j=i;j<n;j+=k){
list.add(arr[j]);
}
Collections.sort(list);
int mid=list.get((list.size())/2);
for(int x:list){
res+=Math.abs(x-mid);
}
}
return res;
}
int gcd(int a,int b){
while(b!=0){
int tmp=b;
b=a%b;
a=tmp;
}
return a;
}