一道无脑的简单题

题目传送门

思路：因为要求最小值，所以我们是删的数越多越好；但如果$\left | a_i-a_{i+1}\right |=1$且$\left | a_{i+1}-a_{i+2}\right|=1$，我们就先删$a_{i+2}$再删$a_{i+1}$，所以我们的代码要从后往前遍历，于是我们得到了这个代码：

#include <iostream>
using namespace std;

int a[500005];

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = n; i > 1; i--) {
		if(abs(a[i] - a[i - 1]) == 1) {
			for(int j = i; j <= n; j++) a[j] = a[j + 1];
			n--;
			i++;
		}
	}
	long long sum = 0;
	for(int i = 1; i <= n; i++) sum += a[i];
	cout << sum << endl;
	return 0;
}

恭喜你得到了80tps

原因：TLE

这是为啥呢？是因为这是$O(n^2)$的算法，所以我们要优化删除操作，于是我想到了——链表

由于作者很懒，懒得写指针链表，于是用了list

介绍一下list：

list是STL容器的其中一种，中文叫链表。 1.头文件：list 2.定义：list<类型> L; list L; 3.加入元素： L.push_front(x):将x插入到最前面 L.push_back(x):将x插入到最后面 pos = L.insert(it, x) 在it位置前插入x 返回值pos为迭代器，指向新元素x的内存空间 4.迭代器： L.begin()指向第一个元素的迭代器 L.end()指向最后一个元素的下一个元素，作为结尾哨兵 list::iterator it = L.begin(); auto it = L.begin(); 可以使用auto来简化代码编写

5.删除元素： L.pop_front():删除第一个元素 L.pop_back():删除最后一个元素 pos = L.erase(it) ：删除it指向元素，it作废。返回值是下一个元素的迭代器 L.erase(first,last) ：删除first到last(不含last)之间的所有元素，最后移除元素之后的迭代器。 6.得到相邻元素：当前为it 上一个元素 it--/--it 下一个元素 it++/++it 扩展： advance(it, x); it移动x个位置，无返回值，直接修改it it = prev(it,x) ;得到it向前移动x位置的迭代器 it = next(it,x) ;得到it向后移动x位置的迭代器

7.补充插入删除 L.insert(it, m, x) 在it前面插入m个x，返回指向首个被插入元素的迭代器，或者在 m = 0 时返回 it。 L.remove(a): 删除L中所有值为a的元素（元素类型需要能判断相等) L.reverse(）翻转L中所有元素，时间复杂度为O(n) 8.剪切 splice

• L.splice(it,L1) 在it前插入L1中所有元素
• L.splice(it,L1,it2)在It前插入L1中it2的对应元素
• L.splice(it,L1,first,last):在it前插入L1中first到last(不含last)的所有元素。

代码：

#include <iostream>
#include <list>
using namespace std;

list<int> a;

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		a.push_back(x); 
	}
	list<int>::iterator pos = a.end();
	pos--;
	for(; pos != a.begin();) {
		int x = *pos;
		pos--;
		int y = *pos;
		if(abs(x - y) == 1) {
			pos = a.erase(++pos);
			n--;
		}
	}
	long long sum = 0;
	pos = a.begin();
	for(; pos != a.end(); pos++) sum += *pos;
	cout << sum << endl;
	return 0;
}