洛谷 P4889 【kls与flag】 题解

对于每一个竿子，你都可以记录下他倒下的点的位置。到这里的思路还是差不多的。但是我们并不需要将每个杆子倒下的位置作为下标来存入数组，而是直接放在数组尾部。当记录完所有杆子后，将他们倒下的位置排一下序，再从头到尾遍历一遍，就可以找出倒下的位置相同的竿子有多少个了。因为两个竿子不可能有两种放倒的方式使他们的顶点重合（显然），因此不会重复。 更具体的见代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,sum,a[200005],num[400005];
long long ans;
int main()
{
    cin>>n>>m;
    for(long long i=1;i<=n;++i)
    {
        cin>>a[i];
        num[++sum]=i-a[i];
        num[++sum]=i+a[i];//将倒下的位置记入数组
    }
    sort(num+1,num+sum+1);//排序
    long long nu=0;
    for(long long i=1;i<=sum;++i)
    {
        if(num[i]!=num[i-1])//当前倒下的位置已经没有竿子了
        {
            ans+=nu*(nu-1)/2;//将倒下位置相同的竿子两两配对
            nu=0;
        }
        nu++;//记录倒在相同位置的竿子有多少个
    }
    ans+=nu*(nu-1)/2;//还剩下最后一个倒下的位置没有判定
    cout<<ans;
    return 0;
}