Codeforces 755 F. PolandBall and Gifts 多重背包+贪心

时间：2022-10-27 04:31:39
F. PolandBall and Gifts
 

It's Christmas time! PolandBall and his friends will be giving themselves gifts. There are n Balls overall. Each Ball has someone for whom he should bring a present according to some permutation p, pi ≠ i for all i.

Unfortunately, Balls are quite clumsy. We know earlier that exactly k of them will forget to bring their gift. A Ball number i will get his present if the following two constraints will hold:

  1. Ball number i will bring the present he should give.
  2. Ball x such that px = i will bring his present.

What is minimum and maximum possible number of kids who will not get their present if exactly k Balls will forget theirs?

Input

The first line of input contains two integers n and k (2 ≤ n ≤ 106, 0 ≤ k ≤ n), representing the number of Balls and the number of Balls who will forget to bring their presents.

The second line contains the permutation p of integers from 1 to n, where pi is the index of Ball who should get a gift from the i-th Ball. For all i, pi ≠ i holds.

Output

You should output two values — minimum and maximum possible number of Balls who will not get their presents, in that order.

Examples
input
5 2
3 4 1 5 2
output
2 4
Note

In the first sample, if the third and the first balls will forget to bring their presents, they will be th only balls not getting a present. Thus the minimum answer is 2. However, if the first ans the second balls will forget to bring their presents, then only the fifth ball will get a present. So, the maximum answer is 4.

 题意：

　　n个人，每个人固定给一个人送一个gift，不会给自己送gift，不会有一个人收到两个gift

　　也就是说，每个人会收到一个gift和送出去一个gift，这样的人ans+1

　　现在你可以指定k个人不会送出去gift

　　ans最小和最大是多少

题解：

　　划分为多个置换群

　　ans最大去贪心就好了

　　最小的话： 如果选取置换群大小相加存在等于k的最小就是k，否则是k+1

　　利用以上：跑背包，是否能构成K，范围太大，需要二进制优化多重背包优化到n*∑log(b[i])，另外bitset优化

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 1e6+, maxn = 1e3+, mod = 1e9+, inf = 2e9;

int a[N],b[N],n,k,vis[N],H[N],cnt;

int main() {

    scanf("%d%d",&n,&k);

    for(int i = ; i <= n; ++i) scanf("%d",&a[i]);

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

        if(vis[i]) continue;

        int j = a[i],cnts = ;

        while(!vis[j]) {

            cnts++;

            vis[j] = ;

            j = a[j];

        }

        b[++cnt] = cnts;

    }

    sort(b+,b+cnt+);

    int ans2 = ,kk = k;

    for(int i = ; i <= cnt; ++i) {

        if(kk >= b[i]/) kk-=b[i]/,ans2 += b[i]/*;

        else {

            ans2 += *kk;

            kk = ;

            break;

        }

    }

    ans2 += kk;

    ans2 = min(n,ans2);

    for(int i = ; i <= cnt; ++i) H[b[i]]++;

    bitset<N> dp;

    dp.set();

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

        if(H[i] == ) continue;

        int t = H[i],l = ;

        while(t) {

            int w = min(t,l);

            t -= w;

            dp |= dp<<(w*i);

            l <<= ;

        }

        if(dp[k] == ) {

            printf("%d %d\n",k,ans2);

            return ;

        }

    }

    printf("%d %d\n",+k,ans2);

    return ;

}

相关文章