Codeforces Round #657

补题进行中

C. Choosing flowers

题意：

你想去买$n$束花，花店现在一共有$m$种不同的花无限供应，第一次买第$i$束花的时候获得$a_i$的快乐值，后来获得$b_i$的快乐值，问如何购买能使获得的快乐值最大。

题解：

最开始的思想必然是贪心的去找一个最大的$b_i$然后把其它大于这个值的$a_i$的花买完了，再回来全部买这一束花，但当我去买两束花的时候，只有这两种花（10,9），（1，10），明显答案是错的。那么贪心不行，那我们再仔细想想，是不是最后只有一种花是重复购买的，而这是必然的，那我们只需要枚举这束花，然后把其它大于它的花都买完，求个最大值。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


const int N=1e5+5;
int a[N],b[N],c[N];
ll pre[N];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n,m;cin>>n>>m;
    _for(i,1,m+1){
      cin>>a[i]>>b[i];
      c[i]=a[i];
    }
    sort(c+1,c+m+1);
    _for(i,1,m+1)pre[i]=pre[i-1]+c[i];
    ll ans=0;
    _for(i,1,m+1){
      ll nn=n;
      int pos=lower_bound(c+1,c+m+1,b[i])-c;
      int mi=min(n,m-pos+1);
      ll t=pre[m]-pre[m-mi];
      nn-=mi;
      if(nn){
        if(pos>m||c[pos]>a[i]){
          t+=a[i];
          nn--;
        }
        t+=nn*b[i];
      }
      ans=max(ans,t);
    }
    cout<<ans<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/12/Codeforces-Round-657/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！