题目链接: 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; }