CF1996F Bomb

前言

大概是一个经典题，只不过比较难想

思路

首先考虑 \(O(k)\) 的做法，很明显，每次我们可以选取一个最大值，然后在把他放回优先队列里面，只不过这样不足以通过此题

而我们又发现只要我们知道最后一次选取的数（第 \(k\) 大）是多少，则前面的数全都可以知道（即对于每个 \(a_i\) ，看比这个数大的数，用等差数列求和）

其实第 \(k\) 大的数明显具有单调性，判断第 \(k\) 大只需要看每个 \(a_i\) 比 \(mid\) 大的数的个数即可

在最后统计答案时候需要注意，可能第 \(k\) 大的数有多个，我们可能只需要选取其中的几个，统计答案时候需要注意

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N];
int n,k;
bool check(int mid)
{
    long long cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=mid)cnt=cnt+1LL*(a[i]-mid)/b[i]+1;
    }
    return cnt>=k;
}
int main()
{
    int _;
    cin>>_;
    while(_--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        int l=0,r=1e9,best=-1;  
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))
            {
                l=mid+1;
                best=mid;
            }
            else r=mid-1;
        }//求第 k 大
	//best 即为第 k 大
        if(best==-1)//特判选不完的情况
        {
            long long ans=0;
            for(int i=1;i<=n;i++)
            {
                long long siz=a[i]/b[i]+1;
                long long h=a[i]-(siz-1)*b[i];
                ans=ans+1LL*(h+a[i])*siz/2;
            }
            cout<<ans<<"\n";
            continue;
        }
        long long ans=0;
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]<best) continue;
            long long cnt=(a[i]-best)/b[i]+1;
            long long h=(a[i]-(cnt-1)*b[i]);
            if(h==best) h+=b[i],cnt--;//先选择大于第 k 大的数
            ans=ans+1LL*(h+a[i])*(cnt)/2;
            sum=sum+1LL*cnt;
        }
        //cout<<sum<<"\n";
        ans=ans+1LL*best*(k-sum);//若不足则用第 k 大补齐即可
        cout<<ans<<"\n";
    }
}
/*
1
5 1000
1 2 3 4 5
5 4 3 2 1
*/