欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[CF1166C]A Tale of Two Lands题解

程序员文章站 2024-03-06 20:41:50
...

比赛的时候lowerbound用错了 现场WA on test4(好吧我承认我那份代码确实有除了lowerbound以外的问题)
于是只能手动二分 (我好菜啊QAQ

经过一波数学推算,我们发现,设序列为\(a\),对于\(a_i\)它不管是正的还是负的答案都是一样的,所以上来我们就珂以给这个数列ABS一下,然后我们拿到了一个正数数列,那么应该怎么求呢?
设有两个序列中的数\(a_x\),\(a_y\)。且我们定义\(a_y<a_x\)。我们发现Arrayland的领土边界为\([a_y,a_x]\),而Vectorland的领土范围为\([a_x-a_y,a_x+a_y]\),注意到因为经过ABS处理的a序列大于等于零,显然\(a_x+a_y \geq a_x\),所以是一定满足的,那么我们只需要考虑左端的情况,为了使\(a_x - a_y \leq a_y\),变形一下显然需要满足\(a_x \leq a_y \times 2\),显然原序列的顺序对答案无影响,所以我们将原序列排序,从头开始枚举每个\(a_y\),显而易见,我们的\(a_x\)只需要在a数组的\([i+1,n]\)范围内二分找出最大的\(k\),使得\(a_k \leq a_i \times 2\),因为原数组排序后的有序性,显而易见a数组中下标小于等于k,大于i的元素都珂以作为\(a_x\),那么当前\(a_y\)对于答案的贡献就是\(k - i\)
完结撒花。

贴个代码:

#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long

using namespace std;

inline ll read(){
    ll x = 0; int zf = 1; char ch = ' ';
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}

ll a[200005];

int main(){
    int n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = abs(read());
    sort(a + 1, a + n + 1);
    ll ans = 0;
    for (int i = 1; i <= n; ++i){
        int l = i + 1, r = n, k = -1, val = a[i] << 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (a[mid] <= val){
                l = mid + 1;
                k = mid;
            }
            else
                r = mid - 1;
        }
        if (k != -1)
            ans += k - i;
    }
    printf("%I64d", ans);
    return 0;
}

上一篇: redisson实现分布式锁原理

下一篇: