[CF1379C] Choosing flowers – 贪心,二分,排序

Description

有 \(m\) 种物品，每种物品第一次买价值为 \(a_i\)，以后每次买都是 \(b_i\)。求买 \(n\) 件物品的最大总价值。\(n \le 10^9, m \le 10^5\)

Solution

容易证明，最多只重复拿一种花，一定不会更劣

假设所有花已经按照 \(a\) 降序排列

设这种花是第 \(i\) 种，则所有被单次选择的 \(j\) 一定满足 \(a_j > b_i\)（等号可取可不取）

故只需求出满足 $a_j > b_i $ 的 \(a_j\) 中前（不超过） \(k-1\) 大的和

在前缀和序列上二分实现，注意如果二分出的选段 \([1,pos]\) 中包含了 \(i\)，则若 \(pos<k-1 \and pos < m \and a[pos+1]>b[i]\) 需要将 \(pos\) 额外 \(+1\)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

struct pr
{
    int a,b;
    bool operator < (const pr &x)
    {
        return a > x.a;
    }
} s[N];

int n,m,a[N],b[N],c[N],d[N];

void solve()
{
    cin>>n>>m;
    for(int i=0;i<=m+2;i++) a[i]=b[i]=c[i]=d[i]=0;
    for(int i=1;i<=m;i++) cin>>s[i].a>>s[i].b;
    sort(s+1,s+m+1);
    for(int i=1;i<=m;i++) a[i]=s[i].a, b[i]=s[i].b, d[i]=-a[i];
    for(int i=1;i<=m;i++) c[i]=c[i-1]+a[i];
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int pos=lower_bound(d+1,d+m+1,-b[i])-d-1;
        pos=min(pos,n-1);
        if(i<=pos && pos<n-1 && pos<m && a[pos+1]>b[i]) ++pos;
        int tmp=c[pos], fg=0;
        if(i<=pos) tmp-=a[i], fg=1;
        tmp+=a[i]+b[i]*(n-1-pos+fg);
        ans=max(ans,tmp);
    }
    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--) solve();
}