codeforces 895B XK Segments 二分思维

codeforces 895B XK Segments
题目大意：
寻找符合要求的$(i,j)$对，有：$$a_i \le a_j $$
同时存在$k$，且$k$能够被$x$整除，$k$满足：$$a_i \le k \le a_j$$
思路：
整体数组排序，对于当前$a_i$寻找符合条件的$a_j$的最大值和最小值
有：$$(a_i-1)/x+k=a_j/x$$
所以可以通过二分查找获得，这里我寻找$((a_i-1)/x+k)*x$为下界，$((a_i-1)/x+k+1)*x$为上界。
注意1：下届需要和$a_i$比较大小，有可能小于$a_i$。上届不需要，它一定大于等于$a_i$
注意2：最后寻找出来的对数和结果会大于$int$，所以使用$long long$
注意3：$scanf$与$cin$不要混用，o(╥﹏╥)o
代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+5;

ll a[maxn];

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    ll n,x,k,cnt;

    cin>>n>>x>>k;

    for(ll i=0;i<n;++i) cin>>a[i];

    sort(a,a+n);

    cnt=0;

    for(ll i=0;i<n;++i) {

        ll l=max(((a[i]-1)/x+k)*x,a[i]);

        ll r=((a[i]-1)/x+k+1)*x;

        cnt+=lower_bound(a,a+n,r)-lower_bound(a,a+n,l);

    }

    cout<<cnt<<endl;

    return 0;

}

巴特西

codeforces 895B XK Segments 二分思维

codeforces 895B XK Segments

题目大意：

思路：

代码：

最新文章

热门文章

巴特西

codeforces 895B XK Segments 二分 思维

codeforces 895B XK Segments

题目大意：

思路：

代码：

最新文章

热门文章

codeforces 895B XK Segments 二分思维