Problem surface

Luogu

preface

At the beginning, I don't want to write this question, because I can't write a linked list (it seems that I haven't written it several times).

Finally, with the encouragement (oppression) of the coach, he made up for his knowledge about the linked list and barely passed the problem.

(after all, the linked list was used in csp D1T3 last year. You have to learn it anyway)

Problem solution

We may think of dp at the beginning, but the scope of this question \ (n \) obviously does not allow dp to pass (but some big guys beat it with two points of WQS and dp by%%%)

In fact, this is a wonderful greed.

Our normal greedy strategy is to choose the big one first.

But you will find that this strategy will be lost by Hack, and you can't even pass the example.

Since the normal greedy thinking is not good, let's have a greedy with repentance.

Because we have chosen a number, those adjacent to it will not be selected.

That is, when we choose a number, if and only if the sum of the left and right numbers is less than this number.

Then we can choose this number and set the value of this number as the difference between the sum of the left and right trees and this number.

If this difference is selected again, it means that we have to choose the number on the left and right sides of it and discard the number in the middle.

Therefore, we need to build a data structure to support the deletion of the left and right sides. The linked list is fully qualified for this job.

As I'm a beginner of linked list, I draw the wrong picture. Please forgive me, QAQ

We maintain a left and right pointer for each block to represent the numbers on its left and right sides.

Suppose we want to delete the elements on the left and right of number five.

We need to point the element to which the left pointer refers, that is, the right pointer of element 3 to element 5.

We then point the right pointer of his right pointer to the element, that is, the left pointer of element 7 to element 5.

Then the left pointer of element 5 points to three and the right pointer points to seven.

We have realized the deletion of the linked list.

The code is as follows:

	int x = L[L[t]], y = R[R[t]];// x represents the element indicated by the left pointer of his left pointer, and y represents the element indicated by the right pointer of his right pointer
	R[x] = t; L[t] = x;//Point the left pointer of point t to X and the right pointer of point x to t
	L[y] = t; R[t] = y;//Point the left pointer of point t to y, and point the left pointer of point y to t

We can use linked lists and heaps to maintain this process.

The code is as follows:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,step,ans,a[200010],used[200010],L[200010],R[200010];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
} 
priority_queue<pair<int,int>,vector<pair<int,int> > >q;
int main()
{
    n = read(); m = read();
    if(m * 2 >  n)//No solution
    {
    	puts("Error!");
    	return 0;
    }
    for(int i = 1; i <= n; i++)
   {
	a[i] = read();
	L[i] = i - 1;
	R[i] = i + 1;
	q.push(make_pair(a[i],i));//At first, put all the points into the big root pile
   }
   R[n] = 1; L[1] = n;
   for(int i = 1; i <= m; i++)
   { 
	int t = q.top().second; q.pop();
 	while(used[t])//If this number is deleted, you need to take a number out of the heap again
	{
		t = q.top().second;
		q.pop();
	}
	ans += a[t];//Plus his contribution
	a[t] = a[L[t]] + a[R[t]] - a[t];//Reset his weight
	used[L[t]] = 1; used[R[t]] = 1; //Mark his left and right sides as deleted
	int x = L[L[t]], y = R[R[t]];//Linked list deletion
	R[x] = t; L[t] = x;
	L[y] = t; R[t] = y;
	q.push(make_pair(a[t],t));
//	R[L[t]] = t; L[R[t]] = t; 
    }
    printf("%d\n",ans);
    return 0;
}

In fact, the linked list can be used. At that time, draw a picture on the examination room and it will come out.