BZOJ4345 POI2016Korale（构造+堆+线段树）

　　注意到k与n同阶，考虑构造一种枚举子集的方式，使得尽量先枚举较小的子集。首先sort一下，用堆维护待选子集。每次取出最小子集，并加入：1.将子集中最大数a_i替换为a_i+1 2.直接向子集中添加a_i+1 这两个子集（若不存在a_i+1则不操作）。如此操作k次即可得到第一问的答案。

　　对于正确性，我们证明当删除一个子集后恰好比他大的下一个子集一定在堆中。采取归纳和反证。显然每个子集都可以由上面的构造方式变换得来。归纳基础显然。假设该子集和比它小的所有子集已被枚举，如果恰好比它大的这个子集不在堆里，则说明可以通过变换得到这个子集的子集均未被枚举，这些子集一定不大于当前子集，这与所有比它小的子集都已枚举矛盾。

　　下面构造方案。只需要算出需要找该总和下第几小的方案，按字典序暴力dfs就可以了，dfs时保证总和不超过第一问的答案即可保证复杂度，找编号最小的可被加入的物品可以用线段树。开始懵逼了半天线段树在这有什么用，然后突然醒悟字典序是读入的而不是排序之后的……没救了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1000010

#define ll long long

int n,m,id[N],b[N],cnt,tot;

int L[N<<],R[N<<],tree[N<<];

ll ans;

struct data

{

    ll x;int i;

    bool operator <(const data&a) const

    {

        return x>a.x;

    }

}a[N];

priority_queue<data> q;

bool cmp(const data&a,const data&b)

{

    return a.i<b.i;

}

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

{

    L[k]=l,R[k]=r;

    if (l==r) {tree[k]=a[l].x;return;}

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    tree[k]=min(tree[k<<],tree[k<<|]);

}

int qmin(int k,int l,int r)

{

    if (L[k]==l&&R[k]==r) return tree[k];

    int mid=L[k]+R[k]>>;

    if (r<=mid) return qmin(k<<,l,r);

    else if (l>mid) return qmin(k<<|,l,r);

    else return min(qmin(k<<,l,mid),qmin(k<<|,mid+,r));

}

int query(int k,int p,ll x)

{

    if (L[k]==R[k]) return L[k];

    int mid=L[k]+R[k]>>;

    if (p>mid) return query(k<<|,p,x);

    else if (qmin(k<<,p,mid)<=x) return query(k<<,p,x);

    else return query(k<<|,mid+,x);

}

void dfs(int k,ll s)

{

    if (tot==) return;

    if (s==ans) {tot--;if (tot==) for (int i=;i<=cnt;i++) printf("%d ",id[i]);return;}

    int p=query(,k+,ans-s);

    while (p<=n)

    {

        id[++cnt]=p;

        dfs(p,s+b[p]);if (tot==) return;

        cnt--;

        p=query(,p+,ans-s);

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4345.in","r",stdin);

    freopen("bzoj4345.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) b[i]=a[i].x=read(),a[i].i=i;

    a[n+].x=,a[n+].i=n+;build(,,n+);

    sort(a+,a+n+);reverse(a+,a+n+);

    q.push((data){a[].x,});

    for (int i=;i<m;i++)

    {

        data x=q.top();q.pop();

        if (x.x>ans) tot=;

        ans=x.x;tot++;

        if (x.i<n) q.push((data){x.x-a[x.i].x+a[x.i+].x,x.i+}),q.push((data){x.x+a[x.i+].x,x.i+});

    }

    cout<<ans<<endl;

    dfs(,);

    return ;

}

巴特西

BZOJ4345 POI2016Korale（构造+堆+线段树）

最新文章

热门文章