宝石（文件I/O）

记 \((l,r)\) 为一个序列内以 \(l\) 为起点的最短合法区间，如果有 \(r\) 随 \(l\) 的增大而增大的话，我们就可以使用尺取法。具体的做法就是不断的枚举 \(l\)，同时求出 \(r\)。因为 \(r\) 随 \(l\) 增大而增大，所以 \(r\) 只有 \(n\) 次变化的机会，所以时间复杂度为\(\Theta(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;
}