[ABC376E] Max × Sum 题解
原题链接
洛谷链接
一道简单的推性质题，首先明确一个性质，子集是非连续的，所以在计算时并不用连续区间求。
拿过题来，首先想的是枚举 \(B\) 的最小子集，但其复杂度为 \(O(C_N^K)\) 复杂度过高，不足以通过本题。于是转变思路，枚举 \(A\) 之中的最大值。若 \(a_i\) 是一个区间最大值，当且仅当长度为 \(k\) 的子集其为最大。但这样还不是很好求。
由于题目未要求输出子集元素，则元素顺序对求解过程无影响，于是建立结构体数组 \(s\) 存储 \(A,B\) ，则有 \(s_i=\{a_i,b_i\}\) ，以 \(a_i\) 的大小进行结构体排序，从大到小遍历数组，建立大根堆维护 \(b_i\) 的，若堆的大小超出 \(k\) 则弹出堆顶，和减去。对于每一个堆的大小等于 \(k\) 的时刻，统计答案。（详见代码）
注：
- 记得开
long long ans的初值不能太小，至少 \(2e17\)
#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long //记得开long long
using namespace std;
const ll maxn = 2e5+10,mod=2e17; //初值至少2e17
ll t,ans;
ll n,k,tot; //tot为b的和
struct node{ll a,b;
}s[maxn];
bool cmp(node a,node b){ //排序函数return a.a<b.a;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){tot=0,ans=mod;priority_queue<ll,vector<ll>,less<ll> >pq; //优先队列存储b的值cin>>n>>k;seq(i,1,n) cin>>s[i].a;seq(i,1,n) cin>>s[i].b;sort(s+1,s+n+1,cmp);seq(i,1,n){if(pq.size()<k-1){ //若堆的大小不足k-1tot+=s[i].b;pq.push(s[i].b);}else{tot+=s[i].b; //压入，正好k个元素pq.push(s[i].b);ans=min(ans,s[i].a*tot); //与原先ans取mintot-=pq.top(); //不确定是否最优，于是继续统计pq.pop();}}cout<<ans<<"\n";}return 0;
}
