既然是pA當然要水水的XD
對於單調隊列和序列單調性有疑問的可以先做這題
這題雙指針和deque當然是都可以的,只是我懶的開陣列(?就邊讀邊做了
(因為輸入有保證是遞增給出,不必sort)
對於點x,往「前」求出所有與他距離不超過d的點們(注意,往前這件事情很重要)
顯然這些點的距離也都不超過d(想一想,為什麼),那麼答案就可以加上C(點數,2);
這件事情就用普通的單調隊列做就行了。
最後要注意的是注意乘法運算,不要溢出。
#define LL long long #include<cstdio> #include<deque> using namespace std; deque<LL> dq; int main() { LL n,d; LL ans=0; scanf("%I64d%I64d",&n,&d); for(LL i=0,x;i<n;i++) { scanf("%I64d",&x); while(dq.size() && x-dq.front()>d) dq.pop_front(); if(dq.size()) ans+=(LL)(dq.size())*(dq.size()-1)/2LL; dq.push_back(x); } printf("%I64d\n",ans); }
沒有留言:
張貼留言