[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\) 的时刻，统计答案。（详见代码）

注：

1. 记得开 long long
2. 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-1
				tot+=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取min
				tot-=pq.top();                    //不确定是否最优，于是继续统计
				pq.pop();
			}
		}
		cout<<ans<<"\n";
	}
    return 0;
}