AT_abc144_e

_7Mr · 2023-08-11 09:30:47 · 题解

题意

有两个数组 a_i 和 f_i 我们可以任意选取若干个 a_i 使他们共减少 k 问怎样减少才能使 \sum_{i=1}^{n} {a_i \times f_i} 最小。

思路

首先我们考虑 k=0 的情况，因为要最小，也就是“一小一大”的搭配，即 a_i 小的与 f_i 大的进行搭配。那么，我们可以将此设定为我们的初始方案，以后的所有方案，均按照此方案为基础。

这时，如果我们题刷得够多，直接一眼丁真 我们可以使用二分，那二分什么呢，我们可以二分 a_i \times f_i。设当前二分到 mid 对于每一个 a_i \times f_i 需要满足 a_i \times f_i \le mid 如果大于，我们就将当前的 a_i 减少到满足，最后判断 k 是否满足此次 mid。

这样我们的大体的结构就出来了，唯一的难点就在于减少多少次才 \le mid。 这也不算是难点 \lceil \frac{a_i \times f_i - mid}{f_i} \rceil。

注：千万不要使用 ceil 函数，不信邪的可以去试试，原因为精度问题。

ACcode

#include<bits/stdc++.h>
#define int long long
#define INF LONG_LONG_MAX
using namespace std;
const int maxn=2e5+5;
int n,k;
int a[maxn],f[maxn];
bool ok(int x){//看此次方案是否能执行
    int res=k;
    for(int i=1;i<=n;i++){
        if(a[i]*f[i]>x) res-=(a[i]*f[i]-x+f[i]-1)/f[i]; 
    } 
    if(res<0) return 0;
    return 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>f[i];
    sort(a+1,a+1+n);//初始方案
    reverse(a+1,a+1+n);
    sort(f+1,f+1+n);
    int l=0,r=INF;
    while(l<=r){//二分
        int mid=(l+r)/2;
        if(ok(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}