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

2021-04-13 12:28

阅读:733

标签:ios   false   des   span   clu   实现   opera   include   names   

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\),则若 \(posb[i]\) 需要将 \(pos\) 额外 \(+1\)

#include 
using namespace std;

#define int long long
const int N = 1000005;

struct pr
{
    int a,b;
    bool operator  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>s[i].a>>s[i].b;
    sort(s+1,s+m+1);
    for(int i=1;ib[i]) ++pos;
        int tmp=c[pos], fg=0;
        if(i>t;
    while(t--) solve();
}

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

标签:ios   false   des   span   clu   实现   opera   include   names   

原文地址:https://www.cnblogs.com/mollnn/p/13341641.html


评论


亲,登录后才可以留言!