[CF1140C]Playlist

Description:

给你n首歌,每首歌有一个长度\(a_i\)和美丽度\(b_i\)
现在可以选出最多k首,动听值为\(\sum a_i*min_{\sum b_i}\)

Hint:

\(n \le 10^5\)

Solution:

只想到了线段树做法,比较麻烦,比赛时没调出来

%%%\(Na_2S_2O_3\)的\(Idea\)

其实就是一个动态维护前k大的过程

我们先把歌曲按\(b_i\)升序排序,分两段处理:

1.从1到k,直接更新答案,同时把对应\(a_i\)扔到小根堆里,维护一个sum表示前k大的和

2.然后每碰到一个\(a_i\),看他是否大于堆顶,大于则替换,否则的话用它的值+sum-堆顶来更新答案

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5;
int n,m,cnt,hd[mxn];

inline int read() {
	char c=getchar(); int x=0,f=1;
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
	return x*f;
}
inline void chkmax(ll &x,ll y) {if(xy) x=y;}

struct ed {
	int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
	t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

struct G { 
	int a,b; 
}T[mxn]; 
  
int cmp(G x,G y) {  
	return x.b>y.b; 
}    

priority_queue , greater > q;

ll ans,sum,k;

int main()
{
	n=read(); k=read();
	for(int i=1;i<=n;++i) {
		T[i].a=read(); T[i].b=read();
	}
	sort(T+1,T+n+1,cmp);
	for(int i=1;i<=k;++i) {
		sum+=T[i].a; q.push(T[i].a);
		chkmax(ans,T[i].b*sum);
	}
	for(int i=k+1;i<=n;++i) {
		if(T[i].a>=q.top()) {
			sum-=q.top()-T[i].a;
			q.pop(); q.push(T[i].a);
			ans=max(1ll*sum*T[i].b,ans);
		}
		else {
			chkmax(ans,(sum-q.top()+T[i].a)*T[i].b);
		}
	}
	printf("%lld",ans);
    return 0;
}

堆贪心

[CF1140C]Playlist

Description:

Hint:

Solution:

相关

map文件堆栈大小

算法第四章《贪心策略》上机实践报告

CDI关于堆栈溢出

《项目经理指导手册》与我的一堆废话·！之一

洛谷 P2279 [HNOI2003]消防局的设立贪心

CF1479B Painting the Array（贪心+DP）

内存泄漏和堆栈溢出的区别

基于堆排序的topk

js栈和堆的区别

数据结构与算法-二叉堆

buuoj [强网杯]随便注（堆叠注入,prepare预定义）

深入解析：Java内存分配之堆、栈和常量池

标签