题解：P14174 【MX-X23-T4】卡常数

qkj_qwq · 2025-10-06 20:20:16 · 题解

解题思路

贪心。

若把 a_{i,j} 替换成 a_{i,j}-b_{i,j}，由于 P_i 是 a_{i,j} 的乘积，所以它会对 P_i 带来贡献的比例是 \dfrac{a_{i,j}-b_{i,j}}{a_{i,j}}。

我们对 \dfrac{b_{i,j}}{a_{i,j}} 进行从大到小排序（即对贡献的比例从小到大排序，即对贡献从大到小排序），就得到了任意一个数列 a_i 的选择的先后顺序。

再定义一个优先队列（大根堆，按对总代价 P 的贡献排序），一开始先把所有数列里，在当前数列里面带来贡献最大的元素全都塞入优先队列里。

然后，优先队列自动排序，筛选出它们里对总代价 P 的贡献最大的元素进行减去 b_{i,j} 操作，再把在当前数列里面带来贡献下一个大的元素（如果有的话）塞入优先队列里。重复筛选 k 次，边筛选边计算答案。

Code

#include<bits/stdc++.h>
#define int long long
#define ll __int128
using namespace std;
int x[500010],l[500010],s[500010],aa[500010],bb[500010],cc[500010];
ll ss[500010];
struct node
{
    double z;int id;
}a[500010];
struct nod
{
    int idx,idy;ll z;
    bool operator<(const nod x)const{return x.z>z;};
};
priority_queue<nod>q;
bool cmp(node xx,node yy){return xx.z>yy.z;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    ll ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>l[i];
        s[i]=s[i-1]+l[i];
        ss[i]=x[i];
        for(int j=1;j<=l[i];j++)cin>>aa[s[i-1]+j],ss[i]*=aa[s[i-1]+j];ans+=ss[i];
        for(int j=1;j<=l[i];j++)cin>>bb[s[i-1]+j];
        for(int j=1;j<=l[i];j++)
        {
            a[j].id=j;
            a[j].z=bb[s[i-1]+j]*1.0/aa[s[i-1]+j];
        }
        sort(a+1,a+l[i]+1,cmp);
        for(int j=1;j<=l[i];j++)cc[s[i-1]+j]=a[j].id;
    }
    for(int i=1;i<=n;i++)
        q.push(nod{i,1,ss[i]/aa[s[i-1]+cc[s[i-1]+1]]*bb[s[i-1]+cc[s[i-1]+1]]});
    while(k--)
    {
        if(q.empty())break;
        nod tp=q.top();
        q.pop();
        int idx=tp.idx;
        int idy=tp.idy;
        int id=s[idx-1]+cc[s[idx-1]+idy];
        ans-=tp.z;
        ss[idx]=ss[idx]/aa[id]*(aa[id]-bb[id]);
        if(idy<l[idx])
        {
            int idd=s[idx-1]+cc[s[idx-1]+idy+1];
            q.push(nod{idx,idy+1,ss[idx]/aa[idd]*bb[idd]});
        }
    }
    cout<<(int)ans;
    return 0;
}