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

Moanran · 2025-10-07 14:22:25 · 题解

题意简述

• 定义数列 a_i 的代价 P_i 为其中所有元素的乘积再乘以 x_i，即

  P_i = x_i \prod_{j=1}^{l_i} a_{i, j} \text{。}

• 定义全体数列的总代价 P 为每个数列的代价之和，即

  P = \sum_{i = 1}^{n} P_i \text{。}

对于所有 P_i 可以修改一共不超过 k 次，让 a_{i, j} 变为 a_{i, j}-b_{i, j} ，最终让 P 最小。

思路分析

考虑贪心，P 为了最小一定要每一个 P_i 小。 首先考虑每一个 P_i，每一次修改相当于对 P_i 乘上一个真分数 \frac{a_{i,j}-b_{i,j}}{a_{i,j}} ,选真分数最小的一定更优，那么相对于整体的 P 计算修改每一个可以给出的差值贡献，并将这个差值放进大根堆，因为 k 小于等于所有序列加起来的总长，直接取全部前 k 个堆顶就好。

AC CODE

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
long long a[500005],b[500005];
priority_queue<long long> Q;
pair<long double,int> ans[500005];
long long result;
int main()
{
    int n,k;
    cin>>n>>k;
    while(n--)
    {
        long long x,l;
        cin>>x>>l;
        long long currmul=x;
        for(int i=1;i<=l;i++)
        {
            cin>>a[i];
            currmul*=a[i];
        }
        result+=currmul;
        for(int i=1;i<=l;i++)
        {
            cin>>b[i];
        }
        for(int i=1;i<=l;i++)
        {
            ans[i].first=1.l*(a[i]-b[i])/a[i];
            ans[i].second=i;
        }
        sort(ans+1,ans+l+1);
        for(int i=1;i<=l;i++)
        {
            long long now=currmul;
            now=currmul/a[ans[i].second]*b[ans[i].second];
            //cout<<currmul-now<<" ";
            Q.push(now);
            currmul-=now;
            //cout<<currmul<<endl;;
        }
    }
    for(int i=1;i<=k;i++)
    {
        //cout<<result<<" ";
        result-=Q.top();
        Q.pop();
    }
    cout<<result;
    return 0;
}