Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist-Toy模板网

这篇具有很好参考价值的文章主要介绍了Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist,日常水题,c++,算法,数据结构

一开始肯定要排个序，b相同时t大的在前边，不同时b大的在前面。

然后想最多只能选k个的限制，可以这样想，每次用到的b只能用已选到的最小的值，那可以把每个b都枚举一遍，然后每一次选时长最长的，且b大于等于当前的b的那k个不就好了吗，时间复杂度也才O（n），然后考虑怎么才能每次快速地选到最大的，这时候就可以考虑优先队列了，每次排序都是logn的复杂度，nlogn，完美。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

const int N = 300010;

int n, k;
struct Node
{
	int a, b;
}songs[N];

bool cmp(Node A, Node B)
{
	if(A.b == B.b)return A.a > B.a;
	return A.b > B.b;
}

int main()
{
	IOS
	cin >> n >> k;
	for(int i = 1; i <= n; i ++)
	{
		cin >> songs[i].a >> songs[i].b;
	}
	
	sort(songs + 1, songs + 1 + n, cmp);
	
	//cout << endl;
	//for(int i = 1; i <= n; i ++)cout << songs[i].a << ' ' << songs[i].b << endl;
	priority_queue<int, vector<int>, greater<int>> q;
	ll ans = 0, res = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(q.size() < k)
		{
			q.push(songs[i].a);
			res += songs[i].a;
		}
		else if(songs[i].a > q.top())
		{
			res -= q.top();
			res += songs[i].a;
			q.pop();
			q.push(songs[i].a);
		}
		
		ans = max(ans, res * songs[i].b);
	}
	cout << ans << endl;
	
	return 0;
}

Problem - 1140C - Codeforces文章来源地址https://www.toymoban.com/news/detail-658335.html

到了这里，关于Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！