Codeforces 1140C(贪心+堆)

题面

传送门

题意:

给出长度为n的序列b,t，定义一个子序列的值为\(\min\{ b_i\} \times \sum t_i\)，求所有子序列中值最大的一个，输出最大值

分析

假如固定某个b[i]，则最大值为\(b_i \times \sum t_j (b_j\geq b_i)\),且t[j]为所有满足条件的t[j]中最大的k个

贪心，先按b[i]从大到小排序

然后从左到右扫描一遍，维护一个最小堆，堆里存储最大的k个数

每次把t[i]插入，如果堆的大小超过k就弹出堆顶，然后更新答案

代码

#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

#define maxn 300005

using namespace std;

struct node{

	int len;

	int beu;

	friend bool operator < (node p,node q){

		return p.beu>q.beu;

	}

}a[maxn];

priority_queue<int,vector<int>,greater<int> >h;

int n,k;

int main(){

	scanf("%d %d",&n,&k);

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

		scanf("%d %d",&a[i].len,&a[i].beu);

	}

	sort(a+1,a+1+n);

	long long sum=0,ans=0;

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

		h.push(a[i].len);

		sum+=a[i].len;

		while(h.size()>k){

			sum-=h.top();

			h.pop();

		}

		ans=max(ans,sum*a[i].beu);

	}

	printf("%I64d\n",ans);

}

巴特西

Codeforces 1140C(贪心+堆)

题面

分析

代码

最新文章

热门文章