记 (l,r) 为一个序列内以 l 为起点的最短合法区间,如果有 r 随 l 的增大而增大的话,我们就可以使用尺取法。具体的做法就是不断的枚举 l,同时求出 r。因为 r 随 l 增大而增大,所以 r 只有 n 次变化的机会,所以时间复杂度为Θ(n)。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=400005;
struct Circle{
int loc, val;//分别表示位置locate和value
}cr[N], qe[N];
bool cmp(Circle p, Circle q){
return p.loc < q.loc;
}
void in(int &x){
char c=getchar();
while (c<'0' || c>'9') c=getchar();
for (x=0; c>='0' && c<='9'; c=getchar())
x=x*10+c-'0';
}
int main(){
freopen("gem.in", "r", stdin);
freopen("gem.out", "w", stdout);
int t;
scanf("%d", &t);
while (t--){
int n, l, k;
scanf("%d %d %d", &n, &l, &k);
for (int i=0; i<n; i++){
in(cr[i].loc); //scanf("%d", &cr[i].loc);
cr[n+i].loc=cr[i].loc+l;//把环拉直,加倍延长处理
}
for (int i=0; i<n; i++){
in(cr[i].val); //scanf("%d", &cr[i].val);
cr[n+i].val=cr[i].val;
}
sort(cr, cr+2*n, cmp);
int front=0, rear=0;//以队列的形式贪心求解(尺取法)
qe[rear].loc=cr[0].loc;
qe[rear].val=cr[0].val;
rear++;
int ans=cr[0].val, sum=cr[0].val;
for (int i=1; i<2*n; i++){
while (front<rear && cr[i].loc-qe[front].loc>k)
sum-=qe[front++].val; //保证在队列内部,loc之差小于k
qe[rear].loc=cr[i].loc;
qe[rear].val=cr[i].val;
rear++;
if (i!=n+front) sum+=cr[i].val;
if (ans<sum) ans=sum;
//printf("%d:%d:%d:%d:%d:%d\n",i,front,rear,cr[i].loc,sum,maxs);
}
printf("%d\n", ans);
}
return 0;
}