Lutece 2152 种海带

题目链接: https://acm.uestc.edu.cn/problem/chong-hai-dai/description

题目大意:给一个圈,挑选了某个节点后相邻的就不能挑了,求最大值

分析:

把选取的点的权值改为两边的和减去中间的,并把两个点删去,这样子一来,这个点就会面临两种情况。

第一种,作为最大值点被选取,那么就意味着放弃了中间而选择两边。设中间点为i,由于i+1和i-1在之前的步骤中已经被删去,所以此时删去的是i-2和i+2,正好符合选取i+1和i-1后不能选取的点。

第二种,作为相邻节点被删去。也就是说,i-2或者i+2中有一个被选取,i-1或i+1无法被选取,只能选取i。

如此一来,就能贪心出最好的结果。

代码:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
struct node
{
	int id, value;
	node(){}
	node(int _id, int _value)
	{
		id = _id; value = _value;
	}
	bool operator <(const node &a)const
	{
		return value < a.value;
	}

}nodes[MAXN];
int isqueue[MAXN],Left[MAXN],Right[MAXN];
int m, n, a,sum=0,leftnode,rightnode;
priority_queue<node> p;
node linshi;
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	memset(isqueue, 0, sizeof(isqueue));
	for (int i = 1; i <= n; ++i)
	{
		cin >> a;
		nodes[i] = node(i, a);
		Left[i] = i - 1; Right[i] = i + 1;
		p.push(nodes[i]);
	}
	Left[1] = n; Right[n] = 1;
	if (m > n / 2)
	{
		cout << "Error!";
	}
	else
	{
		for (int i = 1; i <= m; ++i)
		{
			linshi = p.top(); p.pop();
			while (isqueue[linshi.id])
			{
				linshi = p.top(); p.pop();
			}
			leftnode = Left[linshi.id];
			rightnode = Right[linshi.id];
			isqueue[leftnode] = 1; isqueue[rightnode] = 1;
			Right[Left[leftnode]] = linshi.id;
			Left[Right[rightnode]] = linshi.id;
			Left[linshi.id] = Left[leftnode];
			Right[linshi.id] = Right[rightnode];
			sum += linshi.value;
			nodes[linshi.id].value = nodes[leftnode].value + nodes[rightnode].value - nodes[linshi.id].value;
			linshi.value = nodes[linshi.id].value;
			p.push(linshi);
		}
		cout << sum;
	}
	//system("pause");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注