CodeForces755F 贪心 + 多重背包二进制优化-白红宇

CodeForces755F 贪心 + 多重背包二进制优化

阅读量：4361 次

发布时间：2019-06-07

本文共 2609 字，大约阅读时间需要 8 分钟。

https://cn.vjudge.net/problem/615831/origin

题意

n个人; 计划是每个人都拿一个礼物来送给一个除了自己之外的人; 如果一个人没有送出礼物,那么它和它送礼物的对象都得不到礼物; 但是已经知道有k个人会忘记带礼物来; 问最少有几个人收不到礼物,最多有多少个人收不到礼物

既然是求点和点之间的关系，首先会想到建图，建完图发现事实上图是一个个环状联通快组成的，我们首先对最大值最小值分开进行讨论

最大值：当环是偶数的时候，一个人不送礼物可以提供2个贡献，形成len / 2的贡献，当环是奇数的时候，落单的那一个人需要多一个k去弥补。

所以我们可以贪心的考虑首先将所有人两两配对，每一对用1个花费产生2的贡献，然后在考虑落单的人用1个花费产生1的贡献。

最小值：经过分析可以发现，对于一个环，如果上面有人不送礼物，也就是如果开了这个环，开环的是花费1产生2，之后所有的操作是花费1产生1，如果一个环上的人全部不送礼物，开环产生的多出来的1的贡献可以被消除，所以我们贪心的想到一个环全部扫完了之后再考虑下一个人，如果这个环可以开完，是花费len产生len，如果开不完，是花费len产生len + 1，所以如果K正好可以开满一部分的环，答案就是K，否则答案为K + 1

这就变成了一个多重背包问题，二进制优化一下就可以过了

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair
                     
                      #define PIL pair
                      
                       #define PLL pair
                       
                        #define pb push_back#define fi first#define se second typedef vector
                        
                          VI;const double eps = 1e-9;const int maxn = 1e6 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,tmp,K; int tree[maxn];int SIZE[maxn];int a[maxn];void init(){ For(i,1,N) tree[i] = i,SIZE[i] = 1;}int find(int t){ if(t == tree[t]) return t; return t = find(tree[t]);}void Union(int a,int b){ a = find(a); b = find(b); if(a == b) return; tree[a] = b; SIZE[b] += SIZE[a];}vector
                         
                          bag;vector
                          
                           W;int num[maxn];bool dp[maxn];int main(){ Sca2(N,K); init(); For(i,1,N){ Sca(a[i]); Union(i,a[i]); } For(i,1,N) if(tree[i] == i) bag.pb(SIZE[i]); int cnt = 0,tot = 0; for(int i = 0; i < bag.size(); i++){ if(bag[i] % 2){ cnt++; tot += bag[i] / 2; }else{ tot += bag[i] / 2; } } int MIN,MAX; if(K <= tot) MAX = K * 2; else MAX = tot * 2 + min(cnt,K - tot); for(int i = 0; i < bag.size(); i ++){ num[bag[i]]++; } for(int i = 0 ; i < maxn; i ++){ int k = 1; while(num[i] >= k){ W.pb(i * k); num[i] -= k; k <<= 1; } if(num[i]){ W.pb(i * num[i]); } } dp[0] = 1; for(int i = 0 ; i < W.size(); i ++){ int t = W[i]; for(int j = K; j >= t ;j --){ if(dp[j - t]) dp[j] = 1; } } if(dp[K]) MIN = K; else MIN = K + 1; printf("%d %d",MIN,MAX); #ifdef VSCode system("pause"); #endif return 0;}

转载于:https://www.cnblogs.com/Hugh-Locke/p/9691428.html

你可能感兴趣的文章