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

2021-04-13 12:28

阅读：792

标签：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

上一篇：12.Go语言-网络编程

下一篇：11.Go语言-接口

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[CF1379C] Choosing flowers - 贪心,二分,排序
文章链接：http://soscw.com/index.php/essay/75195.html

亲，登录后才可以留言！

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

Description

Solution

评论

热门文章

推荐文章

最新文章

置顶文章