题解 P1296 【奶牛的耳语】

felixwu · 2018-02-25 22:35:37 · 题解

看到这种题，就要想到队列（毕竟海港都是用队列）。 简单的来说，就是用尺举法。 OK，代码（好看版）：

#include<bits/stdc++.h>
using namespace std;
int q[1000001];
int a[1000001],n,k,r=1,l=1,ans,d;
void push(int x)
{
    r++;
    q[r]=x;
}
void pop()
{
    l++;
}           //两个基本操作，不说了
int main()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    q[r]=a[1]; 
    for(int i=2;i<=n;i++){
        push(a[i]);//入队
        k++;
        while (abs(q[l]-q[r])>d){//没有响应，出队
            pop();
            k--;
        }
        ans+=k;//累计结果
    }
    printf("%d",ans);
    return 0;
}

再来一个压行板：

#include<bits/stdc++.h>
using namespace std;
int q[1000001],a[1000001],n,k,r=1,l=1,ans,d;
int main()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);q[1]=a[1]; 
    for(int i=2;i<=n;i++){
        q[++r]=x;k++;
        while (abs(q[l]-q[r])>d)l++,k--;
        ans+=k;}
    printf("%d",ans);
    return 0;
}