hihocoder #1607 : H星人社交网络(双指针)

传送门

题意

分析

可知对与某个数x，设其可发送信息的边界为[L,R]，那么随着x的递增，[L,R]也右移，故可对输入数排序，做一次双指针即可

trick

代码

//1. Aj < 1/8 * Ai + 8 或者  

//2. Aj > 8 * Ai + 8 或者  

//3. Ai < 88888 且 Aj > 88888  

/*

i不会给j发消息当且仅当

8*a[j]<a[i]+64

a[j]>8*a[i]+8

a[i]<88888&&a[j]>88888

可行区间

1:9~16

2:9~24

9:10~80

10:10~88

11:10~96

...

16:10~136

17:11~144

11110:1397~88888

11112:1397~88888

88888:11103~88888

88889:88888~100000

100000:88888~100000

*/

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

int x,sz;

vector<int>v;

int main()

{

    int n;

    cin>>n;

    F(i,1,n)

    {

        scanf("%d",&x);

        v.push_back(x);

    }

    sort(v.begin(),v.end());

    sz=v.size();

    ll ans=0;

    int l=0,r=-1;

    R(i,0,sz)

    {

        while(l<sz&&v[l]*8<v[i]+64) l++;

        while(r+1<n&&v[r+1]<=8*v[i]+8&&(v[i]>=88888||v[r+1]<=88888)) r++;

        ans+=r-l+1;

        if(i>=l&&i<=r) ans--;

    }

    printf("%lld\n",ans );

    return 0;

}

巴特西

hihocoder #1607 : H星人社交网络(双指针)

传送门

题意

分析

trick

代码

最新文章

热门文章