百题计划-3 codeforces 657div2 C. Choosing flowers 贪心+枚举+二分

https://codeforces.com/contest/1379/problem/C

题意：

给m种花(a,b)，从中取出n朵，每种花可以取0和无限朵，如果取出第i朵花的个数为c>0，则贡献度为ai+(c-1)*bi，如果c=0，则贡献度为0，求最大的贡献度。

解法：

可以看出取了每种花，第0，第1，第2，第3朵，...的贡献度分别是 0，a，b，b，...，

显然，贪心一下，最优方案b取一种（或0），先取比它大的a，最后再取这种b一直取到最后即可。

所以直接枚举最后取哪个b，然后贪心取所有比它大的a（求个前缀和即可），复杂度o(m*logm)。

#include<bits/stdc++.h>

#define sz(v) (int)v.size()

using namespace std;

typedef long long ll;

const int maxn=1000100;

const int INF=(1<<29);

int n,m;

struct Node{

    int a,b;

    ll s;

    friend bool operator<(Node A,Node B){

        return A.a>B.a;

    }

};Node p[maxn];

int bin_a(int l,int r,int b){

    int res=0;

    while(l<=r){

        int m=(l+r)>>1;

        if(p[m].a>=b) res=max(res,m),l=m+1;

        else r=m-1;

    }

    return res;

}

void solve(){

    cin>>n>>m;

    for(int i=1;i<=m;i++) scanf("%d%d",&p[i].a,&p[i].b);

    sort(p+1,p+m+1);

    p[1].s=p[1].a;

    for(int i=2;i<=m;i++) p[i].s=p[i-1].s+p[i].a;

    ll res=0;

    for(int i=1;i<=m;i++){

        int x=bin_a(1,m,p[i].b); // >=b last

        if(x==0){

            res=max(res,1LL*p[i].a+1LL*(n-1)*p[i].b);

            continue;

        }

        if(x>=n){

            res=max(res,p[n].s);

            continue;

        }

        if(x<i) res=max(res,p[x].s+1LL*p[i].a+1LL*(n-x-1)*p[i].b);

        else res=max(res,p[x].s+1LL*(n-x)*p[i].b);

    }

    cout<<res<<endl;

}

int main(){

    // freopen("in.txt","r",stdin);

    int T;cin>>T;

    while(T--) solve();

    return 0;

}

巴特西

百题计划-3 codeforces 657div2 C. Choosing flowers 贪心+枚举+二分

最新文章

热门文章