CF1379C Choosing flowers 题解

解题思路

不是那么显然的，当只选一种 \(b_i\) 或全选 \(a_i\) 时最优。那么我们可以先对 \(a_i\) 从大到小排序，枚举每一个 \(b_i\)，然后二分找到第一个大于等于 \(b_i\) 的 \(a_j\)，判断 \(a_1\sim a_j\) 中是否包含 \(a_i\)，如果包含，当前的答案为 \(\displaystyle \left(\sum_{k=1}^{j} a_k\right)+b_i\times (n-j)\)，否则当前答案为 \(\displaystyle \left(\sum_{k=1}^{j} a_k\right)+a_i+b_i\times (n-j-1)\)，最后对于所有答案取最大值即可。

对于只选一种 \(b_i\) 最优证明如下：

• 若当前 \(b_i\) 最大，若 \(\exists a_j>b_i\)，那么 \(a_j\) 一定位于前缀和中，此时若选择 \(b_i\) 且选择 \(b_j\)，那么可以看作用 \(b_j\) 替换了一个 \(b_i\)，又有 \(b_i>b_j\)，那么答案一定小于只选一种的答案；若 \(a_j<b_i\)，那么一定不会选择用更小的 \(a_j\) 替换更大的 \(b_i\)；
• 若当前 \(b_i\) 不为最大，若 \(\exists a_j>b_i\)，在 \(b_j\) 大于 \(b_i\) 时，全选 \(b_i\) 更优，在 \(b_j<b_i\) 时，同上；若 \(a_j<b_i\)，那么若 \(b_j>b_i\)，则答案一定会在全选 \(b_j\) 或全选 \(b_i\) 中取，证明如上，若 \(b_j<b_i\)，则一定不优；
• 有 \(a_j=b_i\) 或 \(b_j=b_i\) 情况均同上。

综上，只选一种 \(b_i\) 或全选 \(a_i\) 为最优决策，因此可以枚举找到答案。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define N 100005
#define ll long long
int n,m;
struct Flower{
    int a,b;
}a[N];ll sum[N];
inline bool cmp(Flower x,Flower y){
    if(x.a!=y.a)
        return x.a>y.a;
    return x.b>y.b;
}
inline int Upper(int x){
    int l=1,r=m,res=0,mid;
    while(l<=r){
        mid=(l+r+1)>>1;
        if(a[mid].a>=x){
            res=mid;
            l=mid+1;
        }else r=mid-1;
    }return res;
}
inline void work(){
    scanf("%d%d",&n,&m);int k=m;
    int maxt=-1, maxi=0;ll ans=0;
    for(register int i=1;i<=m;++i){
        scanf("%d",&a[i].a);
        scanf("%d",&a[i].b);
        if(a[i].b>maxt) maxt=a[i].b;
    }std::sort(a+1,a+m+1,cmp);
    for(register int i=1;i<=m;++i)
        sum[i]=sum[i-1]+a[i].a;
    if(n<=m) ans=sum[n];
    else ans=sum[m]+1ll*(n-m)*maxt;
    for(register int i=1;i<=m;++i){
        int x=Upper(a[i].b);
        if(x>n) continue;
        ll now=sum[x],res;
        if(x>=i) res=1ll*a[i].b*(n-x);
        else res=a[i].a+1ll*(n-1-x)*a[i].b;
        if(now+res>ans) ans=now+res;
    }printf("%lld\n",ans);
}
signed main(){
    int T;scanf("%d",&T);
    while(T--) work();
}