[CF799E]Aquarium decoration

本文主要是介绍[CF799E]Aquarium decoration，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Aquarium decoration

题解

很容易发现这是个贪心的题

由于直接贪没有什么思路，还是笔者太菜了，我们可以先将所有的材料分成四个部分：

AB都喜欢，A喜欢B不喜欢，B喜欢A不喜欢，AB都不喜欢。

然后，枚举第一部分的选择数量，求出对应的最小值，这部分可以贪心求出。

这样的时间复杂度是的，明显会T，但我们又发现最小值是可以线性推出的。

先将第1部分排序，那在第一部分选的i个一定是选的前i个。于是，在满足两人都喜欢的达到k个的情况下，即第2，3部分都选了个的情况下，就在第2，3，4部分下将剩下还能选的名额分配给现在最小的没选的材料。

每次i增加后，就在第2，3部分根据情况减少一部分，再将其凑满，如果有多的，就根据情况减少即可。

这样时间复杂度就是了，因为还要排序。

源码

好难调啊

 

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define MAXN 500005
typedef long long LL;
#define int LL
typedef pair<LL,int> pii;
const int INF=0x7f7f7f7f7f7f7f7f;
int n,m,k,c[MAXN],la,lb,ans;
bool visa[MAXN],visb[MAXN];
vector<int> vec[5];
signed main(){scanf("%lld %lld %lld",&n,&m,&k);for(int i=1;i<=n;i++)scanf("%lld",&c[i]);scanf("%lld",&la);for(int i=1,x;i<=la;i++)scanf("%lld",&x),visa[x]=1;scanf("%lld",&lb);for(int i=1,x;i<=lb;i++)scanf("%lld",&x),visb[x]=1;for(int i=1;i<=n;i++){if(visa[i]&&visb[i]){vec[1].push_back(c[i]);continue;}if(visa[i]&&!visb[i]){vec[2].push_back(c[i]);continue;}if(!visa[i]&&visb[i]){vec[3].push_back(c[i]);continue;}if(!visa[i]&&!visb[i]){vec[4].push_back(c[i]);continue;}}for(int i=1;i<=4;i++)sort(vec[i].begin(),vec[i].end());int siz=vec[1].size(),sum=0,id1=0,id2=0,id3=0;ans=INF;if(la<k||lb<k){puts("-1");return 0;}if(2*k-siz>m||k>m){puts("-1");return 0;}for(int i=0;i<=siz;i++){if(i)sum+=vec[1][i-1];if(2*k-i>m)continue;if(i>m)break;if(vec[2].size()+i<k||vec[3].size()+i<k)continue;if(i+vec[2].size()+vec[3].size()+vec[4].size()<m)continue;while(i+id1<k)sum+=vec[2][id1],id1++;while(i+id2<k)sum+=vec[3][id2],id2++;//printf("%d %d %d\n",i,id1,id2);while(id1&&id1+i>k){int s1=vec[2][id1-1],s2=INF,s3=INF;if(id2<vec[3].size())s2=vec[3][id2];if(id3<vec[4].size())s3=vec[4][id3];if(s2>s1&&s3>s1)break;if(s2<=s3)sum-=s1-s2,id1--,id2++;else if(s3<s2)sum-=s1-s3,id1--,id3++;}while(id2&&id2+i>k){int s1=INF,s2=vec[3][id2-1],s3=INF;if(id1<vec[2].size())s1=vec[2][id1];if(id3<vec[4].size())s3=vec[4][id3];if(s1>s2&&s3>s2)break;if(s1<=s3)sum-=s2-s1,id1++,id2--;else if(s3<s1)sum-=s2-s3,id3++,id2--;}while(i+id1+id2+id3>m){int s1=0,s2=0,s3=0;if(id1&&i+id1>k)s1=vec[2][id1-1];if(id2&&i+id2>k)s2=vec[3][id2-1];if(id3)s3=vec[4][id3-1];if(s1>=s2&&s1>=s3)sum-=s1,id1--;else if(s2>=s1&&s2>=s3)sum-=s2,id2--;else if(s3>=s1&&s3>=s2)sum-=s3,id3--;}while(i+id1+id2+id3<m){int s1=INF,s2=INF,s3=INF;if(id1<vec[2].size())s1=vec[2][id1];if(id2<vec[3].size())s2=vec[3][id2];if(id3<vec[4].size())s3=vec[4][id3];//printf("%d %lld %lld %lld\n",i,s1,s2,s3);if(s1<=s2&&s1<=s3)sum+=s1,id1++;else if(s2<=s1&&s2<=s3)sum+=s2,id2++;else if(s3<=s1&&s3<=s2)sum+=s3,id3++;}//printf("%d %d %d %d:%d\n",i,id1,id2,id3,sum);ans=min(ans,sum);}printf("%lld\n",ans>INF-1?-1:ans);return 0;
}

谢谢！！！

这篇关于[CF799E]Aquarium decoration的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---