Find the answer

解题思路

要想变0的个数最少，显然是优先把大的变成0。所以离散化，建立一颗权值线段树，维护区间和与区间元素数量，假设至少减去k才能满足条件，查询大于等于k的最少数量即可。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 200005;

struct T{

    int l, r;

    int c;

    ll sum;

}tree[N<<2];

ll a[N], b[N];

void build(int k, int l, int r)

{

    tree[k].l = l, tree[k].r = r;

    tree[k].c = tree[k].sum = 0;

    if(tree[k].l == tree[k].r)

        return;

    int mid = (tree[k].l + tree[k].r) / 2;

    build(2*k, l, mid);

    build(2*k+1, mid + 1, r);

}

void insert(int k, int x)

{

    if(tree[k].l == tree[k].r){

        tree[k].c ++;

        tree[k].sum += b[x];

        return;

    }

    int mid = (tree[k].l + tree[k].r) / 2;

    if(x <= mid)

        insert(2*k, x);

    else

        insert(2*k+1, x);

    tree[k].c = tree[2*k].c + tree[2*k+1].c;

    tree[k].sum = tree[2*k].sum + tree[2*k+1].sum;

}

ll query(int k, ll x)

{

    if(tree[k].l == tree[k].r)

        return (x - 1) / b[tree[k].l] + 1;

    if(tree[2*k+1].sum > x)

        return query(2*k+1, x);

    else if(tree[2*k+1].sum < x){

        x -= tree[2*k+1].sum;

        return query(2*k, x) + tree[2*k+1].c;

    }

    else

        return tree[2*k+1].c;

}

int main()

{

    int q;

    scanf("%d", &q);

    while(q --){

        int n;

        ll m;

        scanf("%d%lld", &n, &m);

        for(int i = 1; i <= n; i ++){

            scanf("%lld", &a[i]);

            b[i] = a[i];

        }

        sort(b + 1, b + n + 1);

        int k = unique(b + 1, b + n + 1) - b - 1;

        build(1, 1, k);

        ll sum = 0;

        for(int i = 1; i <= n; i ++){

            sum += a[i];

            if(sum - m > 0)

                printf("%lld ", query(1, sum - m));

            else

                printf("0 ");

            int x = lower_bound(b + 1, b + k + 1, a[i]) - b;

            insert(1, x);

        }

        printf("\n");

    }

    return 0;

}

巴特西

2019杭电多校第三场hdu6609 Find the answer(线段树)

Find the answer

解题思路

代码如下

最新文章

热门文章