题解 P4393 【[BOI2007]Sequence 序列问题】
小黑AWM
2019-07-24 23:32:05
> 这题很简单，基本的线性贪心我们这里就不再赘述了。不过我们可以通过这题，想到另外一题的做法[【P5462】X龙珠](https://www.luogu.org/problem/P5462)
显然的，我们可以将一个长度为 $n$ 的序列分为 $n-1$ 个二元组，记二元组 $i$ 中的最大值是 $P(i)$ ，每次取出所有二元组 $P(i)$ 最小的那个，把二元组里那个较小的数从序列里删掉，这样子我们其实从二元组集合中删掉了两个元素，又添加了一个元素。
由于一共操作 $n-1$ 次，每次我们从堆中删除一个元素的复杂度是 $O(logn)$ 的，所以复杂度是严格的 $O(nlogn)$ 。
然后用与X龙珠类似的双向链表+堆模拟就可以写出这个做法。
```cpp
/*
* Author: xiaohei_AWM
* Date: 7.24
* Mutto: Face to the weakness, expect for the strength.
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<utility>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
using namespace std;
#define reg register
#define endfile fclose(stdin);fclose(stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
namespace IO{
char buf[1<<15],*S,*T;
inline char gc(){
if (S==T){
T=(S=buf)+fread(buf,1,1<<15,stdin);
if (S==T)return EOF;
}
return *S++;
}
inline int read(){
reg int x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
inline ll readll(){
reg ll x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
}
using namespace IO;
const int maxn = 1e6 + 10;
struct Pair{
int first, second;
int fid, sid;
int maxv(){
return max(first, second);
}
int mid(){
if(first > second) return sid;
else return fid;
}
bool operator<(const Pair &v)const{
return max(first, second) > max(v.first, v.second);
}
};
struct Node{
int num, id, pre, nxt;
} table[maxn];
int n, func[maxn], vi[maxn];
ll ans;
priority_queue<Pair> Q;
int main(){
n = read();
for(int i = 1; i <= n; i++){
table[i].num = read(), table[i].id = i;
table[i].pre = i-1, table[i].nxt = i+1;
}
Pair temp, temp1;
for(int i = 1; i <= n-1; i++){
temp.first = table[i].num;
temp.fid = i;
temp.second = table[table[i].nxt].num;
temp.sid = i+1;
Q.push(temp);
}
while(n > 1){
do{
temp = Q.top();
Q.pop();
}while(vi[temp.fid] || vi[temp.sid]);
n -= 1;
vi[temp.mid()] = 1;
ans = ans + temp.maxv();
table[table[temp.mid()].pre].nxt = table[temp.mid()].nxt;
table[table[temp.mid()].nxt].pre = table[temp.mid()].pre;
temp1.first = table[table[temp.mid()].pre].num,
temp1.second = table[table[temp.mid()].nxt].num;
temp1.fid = table[temp.mid()].pre;
temp1.sid = table[temp.mid()].nxt;
if(temp1.first != 0 && temp1.second != 0)
Q.push(temp1);
}
cout << ans << endl;
return 0;
}
```
没错我就是直接用我过了X龙珠的程序改的。
但是 priority_queue 套了一个比较大的 structure 所以常数不是很优秀，但是用 O2 可以过。读者可以自行采用手写堆优化，或者把函数换成变量之类的。