Codeforces Gym 101291C【优先队列】

题目大意：

就是一道纯模拟题，具体模拟过程见代码。

解题分析：
要掌握不同优先级的优先队列的设置。下面是对优先队列的使用操作详解：

priority_queue<int>q 默认为大顶堆。

priority_queue<int, vector<int>, less<int>> 大顶堆：表示其他都比堆顶小

priority_queue<int, vector<int>, greater<int>> 小顶堆：表示其他都比堆顶大

结构体设置优先级：

只可在结构体内部重载小于号。

两种重置用法：

运算符重载 + 友元

struct fruit

{

    string name;

    double price;

    friend bool operator< (fruit f1, fruit f2)

    {

        return f1.price < f2.price; // 相当于less,这是大顶堆，反之则是小顶堆

    }

} f1, f2, f3; //定义三个结构体变量

这样直接可以：

`priority_queue<fruit > q;

比较运算符外置

struct fruit

{

    string name;

    double price;

} f1, f2, f3; //定义三个结构体变量

struct cmp

{

    bool operator () (fruit f1, fruit f2) // 重载括号

    {

        return f1.price < f2.price; // 等同于less

    }

};

调用语法是：

priority_queue<fruit,vector<fruit> , cmp > q;

这个和基本类型的用法就相似了，只不过是用cmp代替了less或者greater

下面是本题代码：

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long 

int main(){

	int n,m;

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

	int arr[350];

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

		scanf("%d",&arr[i]);

	}

	priority_queue<ll,vector<ll> ,greater<ll> >q;     //将该优先队列设为小顶堆

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

		q.push(arr[i]);

	}

	ll b[350];int cnt=0;

	b[++cnt]=q.top();q.pop();      //挑取刚开始m个中的最小的

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

		q.push(arr[i]);     //将后面没有读过的依次加入

		b[++cnt]=b[cnt-1]+q.top();     //按照题目要求算出每次的值

		q.pop();

	}

	while(q.size()){      //将剩下的所有没读过的全部读完

		b[++cnt]=b[cnt-1]+q.top();

		q.pop();

	}

	ll sum=0;

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

		sum+=b[i];

	}

	printf("%lld\n",sum);

	return 0;

}

2018-09-15

巴特西

Codeforces Gym 101291C【优先队列】

结构体设置优先级：

最新文章

热门文章