自动搬运

查看原文

来自洛谷，原作者为

	Viston **

搬运于2025-08-24 22:04:58，当前版本为作者最后更新于2018-09-23 19:34:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

运用了不用map的方法
即把每个杆子可能落到的位置存进数组
运用sort排序一遍
$O(N)$扫一遍即可

#include<bits/stdc++.h>
using namespace std;
long long a,b,c[200002],d[400002],e=0,i,j,k,l;
int main(){
    ios::sync_with_stdio(false);
    cin>>a>>b;            //O(NlogN),放心用cin
    for(i=1;i<=a;i++){
        cin>>c[i];e+=2;      
        d[e-1]=i-c[i];d[e]=i+c[i];   //入数组
    }
    sort(d+1,d+e+1);         //排序
    for(i=1;i<=2*a;i++){  
        if(d[i]!=d[i-1])       //如果不在这个点了
            k=0;
        else k++,l+=k;         //如果在，就加一下
    }
    cout<<l;                 //输出最后答案
}