CF755F

intel_core · 2022-07-24 22:20:12 · 题解

因为 p_i 是一个排列，所以建出来的图是由若干个环组成的。

第一步显然是并查集把环都拎出来。

先考虑怎么求最大值。

理想情况下，如果一个人没带礼物，那么有两个人收不到礼物。

但如果环长 l 为奇数时，环上有不多于 \frac{l-1}{2} 个人没带礼物时，一个人没带礼物可以让两个人收不到礼物；但当没带礼物的人不少于 \frac{l+1}{2} 时，无论多少人没带都只有 l 个人收不到礼物。

可以建一个大根堆，初始把所有环的环长都放进去；m 次每次取出堆顶的数 x，如果 x>=2 那么答案 +2，并将 x-2 塞回堆里，如果 x=1 那么答案 +1。最后堆中无数或者堆顶为负时停止。

再考虑怎么求最小值。

首先，答案不可能小于 k。

不难发现能取到 k 当且仅当有若干个不同的环的环长之和为 k。

手写 bitset 或者完全背包二进制优化都能做。

复杂度 O(n \log n)。

#pragma GCC optimize("Ofast")
#pragma GCC comment("sse,sse2,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int NR=1e6+10;
int n,m,a[NR],tot,p[NR];

int fa[NR],size[NR];
void init(){
    for(int i=1;i<=n;i++)
        fa[i]=i,size[i]=1;
}
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y){
    x=get(x);y=get(y);
    if(x==y)return;
    fa[x]=y;size[y]+=size[x];
}

int buc[NR],f[NR];
int solve1(){
    for(int i=1;i<=tot;i++)buc[p[i]]++;
    f[0]=1;
    for(int i=1;i<=n;i++)if(buc[i]){
        int now=1,last=buc[i];
        while(1){
            now=min(now,last);
            for(int j=n-i*now;j>=0;j--)
                if(f[j])f[j+i*now]=1;
            if(now==last)break;
            last-=now;now<<=1;
        }
    }
    if(f[m])return m;
    return m+1;
}
int solve2(){
    int res=0;
    priority_queue<int>q;
    for(int i=1;i<=tot;i++)q.push(p[i]);
    for(int i=1;i<=m;i++){
        if(q.empty())break;
        int x=q.top();q.pop();
        res+=min(2,x);
        if(x>2)q.push(x-2);
    }
    return res;
}

int main(){
    cin>>n>>m;init();
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),merge(a[i],i);
    for(int i=1;i<=n;i++)
        if(fa[i]==i)p[++tot]=size[i];
    cout<<solve1()<<" "<<solve2()<<endl;
    return 0;
}