<题目链接>
题目大意：
就是一道纯模拟题，具体模拟过程见代码。
解题分析：
要掌握不同优先级的优先队列的设置。下面是对优先队列的使用操作详解：
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