韩国美食做视频网站,电商运营培训机构,网站建设与管理职业分析,做外贸网站义乌正题 题目大意 nnn个物品#xff0c;有两个人#xff0c;每个人有一些喜欢的物品。
选mmm个物品#xff0c;至少选择kkk个第一个人喜欢的和kkk个第二个人喜欢的物品 解题思路
首先我们必定是选最小的 我们从小到大枚举选择多少两个人都喜欢的物品iii#xff0c;然后每人选…正题 题目大意
nnn个物品有两个人每个人有一些喜欢的物品。
选mmm个物品至少选择kkk个第一个人喜欢的和kkk个第二个人喜欢的物品 解题思路
首先我们必定是选最小的 我们从小到大枚举选择多少两个人都喜欢的物品iii然后每人选择k−xk-xk−x只有这个人喜欢的物品之后我们将剩下的物品丢进一个数据结构里然后求前m−2∗kim-2*kim−2∗ki个最小的物品。
现在我们需要维护一个数据结构支持每次加入一些物品然后求前zzz个最小物品的和。我们发现zzz是每次增加一的可以使用对顶堆保证第一个堆内只有zzz个物品然后每次如果更优就交换两个堆堆顶的数
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N2e510;
priority_queuell q1,q2;
ll n,m,k;
ll ans,cnt,cnt1,cnt2,sum1,sum2,sum,sum0;
ll v[N],a[N],b[N],com[N],p1[N],p2[N];
int main()
{scanf(%lld%lld%lld,n,m,k);for(ll i1;in;i)scanf(%lld,v[i]);ll num;scanf(%lld,num);for(ll i1;inum;i){ll x;scanf(%lld,x);a[x]1;}scanf(%lld,num);for(ll i1;inum;i){ll x;scanf(%lld,x);b[x]1;}for(ll i1;in;i){if(a[i]b[i])com[cnt]v[i];else if(a[i])p1[cnt1]v[i],sum1v[i];else if(b[i])p2[cnt2]v[i],sum2v[i];else q1.push(-v[i]);}sort(com1,com1cnt);sort(p11,p11cnt1);sort(p21,p21cnt2);ans1e18;for(ll i0;imin(cnt,k);i){sumcom[i];while(cnt1k-i){sum1-p1[cnt1];q1.push(-p1[cnt1]);cnt1--;}while(cnt2k-i){sum2-p2[cnt2];q1.push(-p2[cnt2]);cnt2--;}ll nem-cnt1-cnt2-i;if(ne0)continue;if(cnt1i!k||cnt2i!k)continue;while(!q1.empty()q2.size()ne){q2.push(-q1.top());sum0-q1.top();q1.pop();}while(!q1.empty()!q2.empty()-q1.top()q2.top()){ll z1-q1.top(),z2q2.top();q1.pop();q2.pop();sum0z1-z2; q1.push(-z2);q2.push(z1);}if(q2.size()ne)ansmin(ans,sum0sumsum1sum2);}if(ans1e18)printf(-1);else printf(%lld,ans);
}
