2017年10月20日提高T3 編譯優化

2017年10月20日提高T3 編譯優化

Description


這裡寫圖片描述

Input


這裡寫圖片描述

Output


這裡寫圖片描述

Hint


這裡寫圖片描述
這裡寫圖片描述

Solution


可以撤銷的貪心,妙啊

考試的時候沒想到,思路很神奇。
貪心地做,用一個堆維護最大的點。由於不能連續地選,那麼我們選了一個點i之後就刪掉前面的點pre[i]和後面的點nex[i]。但是這樣會錯因為不一定是最優的,於是需要每次刪點之後新建一個權值為v[pre[i]] v[nex[i]]-v[i]的點,表示選了pre[i]和nex[i]而不選i,意味著只選i的操作是可以撤銷的。這樣每次一定多選一個點,選完m個一定是最優的

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <queue>
#define rep(i, st, ed) for (int i = st; i <= ed; i  = 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define erg(i, st) for (int i = ls[st]; i; i = e[i].next)
#define fill(x, t) memset(x, t, sizeof(x))
#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))
#define abs(x) ((x)<(0)?(-(x)):(x))
#define N 202000
#define E 1001
#define L 1001
using std:: pair;
std:: priority_queue<pair <int, int> > heap;
int pre[N], nex[N], t[N];
bool vis[N];
inline int read() {
int x = 0, v = 1; char ch = getchar();
for(; ch<'0'||ch>'9'; v=(ch=='-')?(-1):(v),ch=getchar());
for(; ch<='9'&&ch>='0'; (x*=10) =ch-'0',ch=getchar());
return x * v;
}
int main(void) {
int n = read();
int m = read();
rep(i, 1, n) {
t[i] = read();
pre[i] = i - 1;
nex[i] = i   1;
pair <int, int> p(t[i], i);
heap.push(p);
}
pre[1] = n;
nex[n] = 1;
int ans = 0;
rep(i, 1, m) {
pair <int, int> top(heap.top());
heap.pop();
while (vis[top.second]) {
top = heap.top();
heap.pop();
if (heap.empty()) {
puts("Error!");
return 0;
}
}
ans  = top.first;
t[top.second] = t[pre[top.second]]   t[nex[top.second]] - t[top.second];
vis[pre[top.second]] = vis[nex[top.second]] = 1;
nex[pre[pre[top.second]]] = top.second;
pre[top.second] = pre[pre[top.second]];
pre[nex[nex[top.second]]] = top.second;
nex[top.second] = nex[nex[top.second]];
heap.push(std:: make_pair(t[top.second], top.second));
}
printf("%d\n", ans);
return 0;
}