贪心算法：
STL优先队列实现最大堆，最小堆
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include<iostream>
#include<queue>
using
namespace
std;
const
int
MAX=1001;
int
a[MAX];
int
calPrize(
int
n,
int
x)
{
int
start=n-x+1;
return
(start+n)*x/2;
}
int
fun(
int
n,
int
m,
int
pos[])
{
priority_queue<
int
,vector<
int
>,greater<
int
> >heap;
//最小堆
priority_queue<
int
,vector<
int
>,less<
int
> >heap2;
//最大堆
for
(
int
i=0;i<m;i++)
{
heap.push(pos[i]);
heap2.push(pos[i]);
}
int
ret1=0,ret2=0;
for
(
int
i=0;i<n;i++)
{
int
tmp=heap.top();
ret1+=tmp;
heap.pop();
if
(tmp>1)
heap.push(tmp-1);
tmp=heap2.top();
ret2+=tmp;
heap2.pop();
if
(tmp>1)
heap2.push(tmp-1);
}
cout<<ret2<<
" "
<<ret1<<endl;
}
int
main()
{
int
n, m;
cin>>n>>m;
for
(
int
i=0;i<m;i++)
cin>>a[i];
fun(n,m,a);
//cin>>m;
}
|
本文转自博客园知识天地的博客，原文链接：codeforces上一道贪心算法题，如需转载请自行联系原博主。
