NKOJ 3102 取数（堆）

发表于 |
字数统计: 630字 | 阅读时长 ≈ 3min

P3102取数

问题描述

n个整数组成的一个环，现在要从中取出m个数，取走一个数字就不能取跟它相邻的数字(相邻的数不能同时取)。要求取出的数字的总和尽可能大，问这个最大和是多少？ 如果无解，请输出“Error!”

输入格式

第一行包含两个正整数n、m。
第二行为n个整数Ai。

输出格式

仅一个整数，表示所求结果。如果无解输出“Error!”，不包含引号。

样例输入

8 4 
8 5 6 2 3 4 8 9

样例输出

25

提示

对于全部数据：m<=n；-1000<=Ai<=1000
N<=200000

此题容易想到dp，然而dp的复杂度是$n^2$的，显然不能通过。
正解是用堆维护。
我们将每个元素编号1-tot，记录它左边元素，右边元素，本身的值。
将它的值和编号加入堆中，每次取出堆顶可用元素，将它，它左边元素，它右边元素标记为不可用。
这样做显然是不对的，因为我们无法解决$2 \ 4 \ 3$这种情况。
为了解决这种情况，我们每次取出一个点后，要向堆中加入一个点，
这个点的编号是tot++，值等于左边元素+右边元素-中间元素。
这个点代表的意义就是选择左边元素和右边元素，而不选择中间元素。

代码：

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
46
47
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<deque>
using namespace std;
struct node{int d,x;};
bool operator<(node a,node b)
{return a.x<b.x;}
priority_queue<node>Q;
int i,ans,n,m,x,y,tot;
int A[2000005],L[2000005],R[2000005];
bool mark[2000005];
node tmp,temp;
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	if(m>n/2){puts("Error!");return 0;}
	L[1]=n;R[1]=2;tmp.d=1;tmp.x=A[1];Q.push(tmp);
	L[n]=n-1;R[n]=1;tmp.d=n;tmp.x=A[n];Q.push(tmp);
	for(i=2;i<n;i++)
	{
		L[i]=i-1;
		R[i]=i+1;
		tmp.d=i;
		tmp.x=A[i];
		Q.push(tmp);
	}
	tot=n;
	for(i=1;i<=m;i++)
	{
		tmp=Q.top();
		Q.pop();
		x=tmp.d;
		if(mark[x]){i--;continue;}
		ans+=A[x];
		A[++tot]=A[L[x]]+A[R[x]]-A[x];
		L[tot]=L[L[x]];R[L[L[x]]]=tot;
		R[tot]=R[R[x]];L[R[R[x]]]=tot;
		temp.x=A[tot];temp.d=tot;
		Q.push(temp);
		mark[L[x]]=mark[R[x]]=mark[x]=1;
	}
	cout<<ans;
}