没处理一个元素,就要维护他旁边的差
const int N = 100010; typedef pair<LL, int> PLI; priority_queue<PLI, vector<PLI>, greater<PLI> > Q; int n, m; LL Dat[N]; int L[N], R[N]; bool Okay[N]; inline void Input() { scanf("%d%d", &n, &m); For(i, 1, n) scanf("%I64d", &Dat[i]); } inline void Solve() { /* Init Begin */ Dat[n+1] = Dat[0] = MLL, Okay[0] = 1; For(i, 1, n) Dat[i] = Dat[i+1]-Dat[i], L[i] = i-1, R[i] = i+1, Q.push(PLI(Dat[i], i)); LL Ans = 0; /* Init End */ while(m--) { int Top = 0; while(Okay[Top]) Top = Q.top().sd, Q.pop(); int l = L[Top], r = R[Top]; Okay[l] = Okay[r] = 1; Ans += Dat[Top]; R[L[l]] = L[R[r]] = Top, Dat[Top] = Dat[l]+Dat[r]-Dat[Top]; L[Top] = L[l], R[Top] = R[r]; Q.push(PLI(Dat[Top], Top)); } cout << Ans << endl; } int main() { #ifndef ONLINE_JUDGE SETIO("1150"); #endif Input(); Solve(); return 0; }
相关推荐
八中OJ,又简作BZOJ,以原题巨多而著称,该数据为BZOJ上的1000-1109和1130-1139的测试数据节点,没有题目,有需要题目的可以到https://hydro.ac/d/bzoj/p网站查找对应的题目。
CTSC 2011 无穷图的桥(BZOJ 2307) 题解.ppt
BZOJ3230相似子串的测试数据,希望能够帮到大家。
BZOJ题目以及数据
bzoj部分数据.
bzoj1878数据(莫队)详细题解:http://blog.csdn.net/boyxiejunboy/article/details/50611972
BZOJ原题-BZOJP3001-P4000的题目,下载后可以离线做题。
bzoj1000到1079所有题目的测试数据,不需花费积分!!!很有用的!oj建立者们可以用来添加题目!
bzoj1140到1149所有题目的测试数据,不需花费积分!!!很有用的!oj建立者们可以用来添加题目!
bzoj1080到1099所有题目的测试数据,不需花费积分!!!很有用的!oj建立者们可以用来添加题目!
bzoj1110到1129所有题目的测试数据,不需花费积分!!!很有用的!oj建立者们可以用来添加题目!
bzoj1100到1109所有题目的测试数据,不需花费积分!!!很有用的!oj建立者们可以用来添加题目!
bzoj1130到1139所有题目的测试数据,不需花费积分!!!很有用的!oj建立者们可以用来添加题目!
BZOJ原题-BZOJP1000-P2000的题目,下载后可以离线做题。
BZOJ平台全部代码,解压到一个文件夹在打开使用。BZOJ平台全部代码,解压到一个文件夹在打开使用。
「BZOJ1053」反素数/「Violet5」樱花 详细题解
CreationAugust 的BZOJ代码合集 【Written by CreationAugust】
BZOJ原题-BZOJP2001-P3000的题目,下载后可以离线做题。
BZOJ原题-BZOJP4001-P4406的题目,下载后可以离线做题。
BZOJ网站镜像,对于经常挂掉的BZOJ真是刷题必备啊!