http://acm.fzu.edu.cn/problem.php?pid=1858
一个数组中 找两对元素，第一对元素和最大，第二对元素和最小，限制:一对元素中两个元素的距离在原数组中小于d。去掉这两对元素，剩下的求平均值。
思路：先找两个最大的，暴力枚举第一对元素的最后一个元素，然后维护一个单调减队列，反之 就是维护单调增队列。复杂度O（n）.
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
const int INF=0x7fffffff;
const double EPS=1e-;
const int maxn=+;
int q[maxn],a[maxn],n,d;
int main()
{
while(~scanf("%d%d",&n,&d))
{
double ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
ans+=a[i];
}
int f=,r=,last,sum=-INF;
q[++r]=;
last=;
while(last<=n)
{
while(f<=r&&last-q[f]>=d)f++;
if(f<=r&&sum<a[q[f]]+a[last])sum=a[q[f]]+a[last];
while(f<=r&&a[last]>=a[q[r]])r--;
q[++r]=last++;
}
ans-=sum;
f=;
r=;
sum=INF;
last=;
while(last<=n)
{
while(f<=r&&last-q[f]>=d)f++;
if(f<=r&&sum>a[q[f]]+a[last])sum=a[q[f]]+a[last];
while(f<=r&&a[last]<=a[q[r]])r--;
q[++r]=last++;
}
ans-=sum;
printf("%.3f\n",ans/(n-));
}
return ;
}