【题目链接】:http://codeforces.com/contest/755/problem/F
【题意】
n个人;
计划是每个人都拿一个礼物来送给一个除了自己之外的人;
且如果一个人没有送出礼物,那么它和它送礼物的对象都得不到礼物;
但是已经知道有k个人会忘记带礼物来;
问最少有几个人收不到礼物,最多有多少个人收不到礼物
【题解】
①
对于最多的情况;
最后会形成多个环;
每个环隔一个人选一个人忘记带礼物;这样一个长度为len的环只要len/2个人没带礼物就能够整个环的人都收不到礼物了;
然后如果len为奇数就放在最后再处理;因为那些多余的一个人必须得用1个名额来补充;所以先放在最后;因为你当前一个名额能够抵消两个人,肯定优先抵消两个人;
②
对于最少的情况;
就是k个名额刚好分配每个环的人数;
如果不是刚好;
则会多出一个人即k+1
那么问题就转换成一个背包问题了;
把每个环的长度看成一个物品,同种长度的环可能有多个
->多重背包;
问能不能刚好体积为k;
这里用到了多重背包的二进制优化;
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,k,vis[maxn],a[maxn],b[maxn],c[maxn],d[maxn];
bool dp[maxn];
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int ans1=k,ans2=0,cnt=0;for(int i=1;i<=n;i++){if(vis[i])continue;int number=0,p=i;while(!vis[p]){vis[p]=1;number++;p=a[p];}b[++cnt]=number;}sort(b+1,b+cnt+1);int kk=k,num=0;for(int i=1;i<=cnt;++i){if(b[i]/2<=kk)ans2+=b[i]/2*2,kk-=b[i]/2;else ans2+=2*kk,kk=0;if(b[i]&1)num++;}ans2+=min(kk,num);num=0;int number=0;for(int i=1;i<=cnt;++i){if(b[i]==b[i-1])d[num]++;else d[++num]=1,a[num]=b[i];}cnt=0;for(int i=1;i<=num;++i){for(int j=1;d[i];j<<=1){int tep=min(d[i],j);c[++cnt]=a[i]*tep;d[i]-=tep;}}dp[0]=true;for(int i=1;i<=cnt;++i)for(int j=k-c[i];j>=0;--j)if(dp[j])dp[j+c[i]]=true;if(!dp[k])ans1++;printf("%d %d\n",ans1,ans2);return 0;
}