首页 > 其他分享 >AtCoder Regular Contest 119 E Pancakes

AtCoder Regular Contest 119 E Pancakes

时间：2023-05-01 20:23:29浏览次数：42  
标签：node AtCoder return Pancakes mid else Regular const op

洛谷传送门

AtCoder 传送门

感觉挺典的，为啥有 2500 啊（

观察发现，反转序列对 \(\sum\limits_{i=1}^{n-1} |a'_i - a'_{i+1}|\) 影响不大。具体而言，设反转了 \(a_l \sim a_r\)，记 \(s = \sum\limits_{i=1}^{n-1} |a_i - a_{i+1}|\)，那么 \(s' = s - |a_{l-1} - a_l| - |a_r - a_{r+1}| + |a_l - a_{r+1}| + |a_{l-1} - a_r|\)（特判 \(l = 1 \lor r = n\)）。

则现在就是要找到一组 \((l,r), 2 \le l \le r < n\)，使得 \(s'\) 最小。对后两项拆绝对值之后化成三维偏序的形式，因此跑四遍 cdq 即可。

时间复杂度 \(O(n \log^2 n)\)。cdq 内使用归并排序、树状数组，可以通过。

code 
// Problem: E - Pancakes
// Contest: AtCoder - AtCoder Regular Contest 119
// URL: https://atcoder.jp/contests/arc119/tasks/arc119_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 600100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, a[maxn], b[maxn], sum, ans, lsh[maxn], tot, m;
struct node {
	ll x, y, z, op;
	node(ll a = 0, ll b = 0, ll c = 0, ll d = 0) : x(a), y(b), z(c), op(d) {}
} p[maxn], q[maxn];

inline bool cmp1(const node &a, const node &b) {
	if (a.x != b.x) {
		return a.x < b.x;
	} else if (a.y != b.y) {
		return a.y < b.y;
	} else if (a.z != b.z) {
		return a.z < b.z;
	} else {
		return a.op < b.op;
	}
}

inline bool cmp2(const node &a, const node &b) {
	if (a.x != b.x) {
		return a.x < b.x;
	} else if (a.y != b.y) {
		return a.y < b.y;
	} else if (a.z != b.z) {
		return a.z > b.z;
	} else {
		return a.op < b.op;
	}
}

inline bool cmp3(const node &a, const node &b) {
	if (a.x != b.x) {
		return a.x < b.x;
	} else if (a.y != b.y) {
		return a.y > b.y;
	} else if (a.z != b.z) {
		return a.z < b.z;
	} else {
		return a.op < b.op;
	}
}

inline bool cmp4(const node &a, const node &b) {
	if (a.x != b.x) {
		return a.x < b.x;
	} else if (a.y != b.y) {
		return a.y > b.y;
	} else if (a.z != b.z) {
		return a.z > b.z;
	} else {
		return a.op < b.op;
	}
}

namespace BIT {
	ll c[maxn];
	
	inline void init() {
		mems(c, 0x3f);
	}
	
	inline void clear(int x) {
		for (int i = x; i <= tot; i += (i & (-i))) {
			c[i] = inf;
		}
	}
	
	inline void update(int x, ll d) {
		for (int i = x; i <= tot; i += (i & (-i))) {
			c[i] = min(c[i], d);
		}
	}
	
	inline ll query(int x) {
		ll res = inf;
		for (int i = x; i; i -= (i & (-i))) {
			res = min(res, c[i]);
		}
		return res;
	}
}

void cdq1(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) >> 1, i = l, j = mid + 1, t = 0;
	cdq1(l, mid);
	cdq1(mid + 1, r);
	while (i <= mid && j <= r) {
		if (p[i].y <= p[j].y) {
			if (p[i].op == 1) {
				BIT::update(p[i].z, -b[p[i].x - 1] - a[p[i].x] - a[p[i].x - 1]);
			}
			q[++t] = p[i++];
		} else {
			if (p[j].op == 2) {
				ans = min(ans, sum + BIT::query(p[j].z) - b[p[j].x] + a[p[j].x + 1] + a[p[j].x]);
			}
			q[++t] = p[j++];
		}
	}
	while (i <= mid) {
		if (p[i].op == 1) {
			BIT::update(p[i].z, -b[p[i].x - 1] - a[p[i].x] - a[p[i].x - 1]);
		}
		q[++t] = p[i++];
	}
	while (j <= r) {
		if (p[j].op == 2) {
			ans = min(ans, sum + BIT::query(p[j].z) - b[p[j].x] + a[p[j].x + 1] + a[p[j].x]);
		}
		q[++t] = p[j++];
	}
	for (int i = l; i <= mid; ++i) {
		if (p[i].op == 1) {
			BIT::clear(p[i].z);
		}
	}
	for (int i = 1; i <= t; ++i) {
		p[l + i - 1] = q[i];
	}
}

void cdq2(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) >> 1, i = l, j = mid + 1, t = 0;
	cdq2(l, mid);
	cdq2(mid + 1, r);
	while (i <= mid && j <= r) {
		if (p[i].y <= p[j].y) {
			if (p[i].op == 1) {
				BIT::update(tot - p[i].z + 1, -b[p[i].x - 1] - a[p[i].x] + a[p[i].x - 1]);
			}
			q[++t] = p[i++];
		} else {
			if (p[j].op == 2) {
				ans = min(ans, sum + BIT::query(tot - p[j].z + 1) - b[p[j].x] + a[p[j].x + 1] - a[p[j].x]);
			}
			q[++t] = p[j++];
		}
	}
	while (i <= mid) {
		if (p[i].op == 1) {
			BIT::update(tot - p[i].z + 1, -b[p[i].x - 1] - a[p[i].x] + a[p[i].x - 1]);
		}
		q[++t] = p[i++];
	}
	while (j <= r) {
		if (p[j].op == 2) {
			ans = min(ans, sum + BIT::query(tot - p[j].z + 1) - b[p[j].x] + a[p[j].x + 1] - a[p[j].x]);
		}
		q[++t] = p[j++];
	}
	for (int i = l; i <= mid; ++i) {
		if (p[i].op == 1) {
			BIT::clear(tot - p[i].z + 1);
		}
	}
	for (int i = 1; i <= t; ++i) {
		p[l + i - 1] = q[i];
	}
}

void cdq3(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) >> 1, i = l, j = mid + 1, t = 0;
	cdq3(l, mid);
	cdq3(mid + 1, r);
	while (i <= mid && j <= r) {
		if (p[i].y >= p[j].y) {
			if (p[i].op == 1) {
				BIT::update(p[i].z, -b[p[i].x - 1] + a[p[i].x] - a[p[i].x - 1]);
			}
			q[++t] = p[i++];
		} else {
			if (p[j].op == 2) {
				ans = min(ans, sum + BIT::query(p[j].z) - b[p[j].x] - a[p[j].x + 1] + a[p[j].x]);
			}
			q[++t] = p[j++];
		}
	}
	while (i <= mid) {
		if (p[i].op == 1) {
			BIT::update(p[i].z, -b[p[i].x - 1] + a[p[i].x] - a[p[i].x - 1]);
		}
		q[++t] = p[i++];
	}
	while (j <= r) {
		if (p[j].op == 2) {
			ans = min(ans, sum + BIT::query(p[j].z) - b[p[j].x] - a[p[j].x + 1] + a[p[j].x]);
		}
		q[++t] = p[j++];
	}
	for (int i = l; i <= mid; ++i) {
		if (p[i].op == 1) {
			BIT::clear(p[i].z);
		}
	}
	for (int i = 1; i <= t; ++i) {
		p[l + i - 1] = q[i];
	}
}

void cdq4(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = (l + r) >> 1, i = l, j = mid + 1, t = 0;
	cdq4(l, mid);
	cdq4(mid + 1, r);
	while (i <= mid && j <= r) {
		if (p[i].y >= p[j].y) {
			if (p[i].op == 1) {
				BIT::update(tot - p[i].z + 1, -b[p[i].x - 1] + a[p[i].x] + a[p[i].x - 1]);
			}
			q[++t] = p[i++];
		} else {
			if (p[j].op == 2) {
				ans = min(ans, sum + BIT::query(tot - p[j].z + 1) - b[p[j].x] - a[p[j].x + 1] - a[p[j].x]);
			}
			q[++t] = p[j++];
		}
	}
	while (i <= mid) {
		if (p[i].op == 1) {
			BIT::update(tot - p[i].z + 1, -b[p[i].x - 1] + a[p[i].x] + a[p[i].x - 1]);
		}
		q[++t] = p[i++];
	}
	while (j <= r) {
		if (p[j].op == 2) {
			ans = min(ans, sum + BIT::query(tot - p[j].z + 1) - b[p[j].x] - a[p[j].x + 1] - a[p[j].x]);
		}
		q[++t] = p[j++];
	}
	for (int i = l; i <= mid; ++i) {
		if (p[i].op == 1) {
			BIT::clear(tot - p[i].z + 1);
		}
	}
	for (int i = 1; i <= t; ++i) {
		p[l + i - 1] = q[i];
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i < n; ++i) {
		b[i] = abs(a[i] - a[i + 1]);
		sum += b[i];
	}
	ans = sum;
	for (int i = 2; i < n; ++i) {
		ans = min(ans, sum - b[i] + abs(a[1] - a[i + 1]));
	}
	for (int i = n - 1; i >= 2; --i) {
		ans = min(ans, sum - b[i - 1] + abs(a[n] - a[i - 1]));
	}
	for (int i = 1; i <= n; ++i) {
		lsh[++tot] = a[i];
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 2; i < n; ++i) {
		int x = lower_bound(lsh + 1, lsh + tot + 1, a[i - 1]) - lsh;
		p[++m] = node(i, a[i], x, 1);
	}
	for (int i = 2; i < n; ++i) {
		int x = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
		p[++m] = node(i, a[i + 1], x, 2);
	}
	BIT::init();
	sort(p + 1, p + m + 1, cmp1);
	cdq1(1, m);
	sort(p + 1, p + m + 1, cmp2);
	cdq2(1, m);
	sort(p + 1, p + m + 1, cmp3);
	cdq3(1, m);
	sort(p + 1, p + m + 1, cmp4);
	cdq4(1, m);
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签：node,AtCoder,return,Pancakes,mid,else,Regular,const,op
From： https://www.cnblogs.com/zltzlt-blog/p/17366944.html

相关文章

  • AtCoder Regular Contest 117 D Miracle Tree
    洛谷传送门AtCoder传送门第一步就没想到可以考虑化简限制。设所有点按\(E_i\)从小到大排序后顺序是\(p_1,p_2,...,p_n\)。发现只需满足\(E_{p_{i+1}}-E_{p_i}\ge\operatorname{dis}(p_i,p_{i+1})\)。证明是对于任意\(i<j<k\)，若\(p_i,p_j\)和\(p_j,p_k\)均满......
  • AtCoder Beginner Contest 231
    A-WaterPressure#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn; cin>>n; printf("%.6lf\n",n/100.0);return0;}B-Election#include<bits/stdc++.h>usingnamespacestd;intmain(){ ios:......
  • AtCoder比赛记录（一）
    这里记录的是这个账号的比赛情况。ARC1572023-2-25Solved:4/62189->2216C(Medium,1802)给定一个XY矩阵，一条左上角到右下角的路径的分值定义为路径上连续两个Y的组数。求所有可能路径的分值的平方和。Solution：经典DP。递推两个量，一个是到(i,j)所有路径的分值和\(f_{i,j}\)，......
  • AtCoder比赛记录（二）
    这里记录的是这个账号的比赛情况。ABC3002023-4-29Solved:7/80->1200F(Medium-,1846)给定由o和x组成的字符串\(S\)。将\(S\)复制\(m\)遍，然后将其中\(k\)个x改成o，求改完之后连续的o最多可能有多少个。Solution：贪心。设最多能改完\(t\)个完整的\(S\)，考虑三类情况：最长连续......
  • AtCoder Regular Contest 116 F Deque Game
    洛谷传送门AtCoder传送门很强的博弈+性质题。下文令A为Takahashi，B为Aoki。发现单独考虑一个序列\(a_1,a_2,...,a_n\)：若\(n\bmod2=0\)：若A为先手，答案为\(\max(a_{\frac{n}{2}},a_{\frac{n}{2}+1})\)；若B为先手，答案为\(\min(a_{\frac{n}{2}},a_{\frac......
  • AtCoder Regular Contest 123 E Training
    洛谷传送门AtCoder传送门不妨假设\(B_X\leB_Y\)。设\(f(x)=A_X+\frac{x}{B_X},g(x)=A_Y+\frac{x}{B_Y},F(x)=\left\lfloor{f(x)}\right\rfloor,G(x)=\left\lfloor{g(x)}\right\rfloor\)，题目即求\(\sum\limits_{x=1}^n[F(x)=G(x)]\)。我一开始尝试化简......
  • AtCoder Regular Contest 126 E Infinite Operations
    洛谷传送门AtCoder传送门算是对这篇博客的补充吧。设\(a_1\lea_2\le\cdots\lea_n\)。发现最优操作中一定是对相邻的数进行操作，因为如果\(a_j\)想把\(x\)给\(a_i\)（\(i<j\)），最优是依次操作\((j-1,j,x),(j-2,j-1,x),...,(i,i+1,x)\)。这样\(x\)就能造成\((j-i)......
  • 【AtCoder】Forbidden Pattern
    题目链接分析首先考虑哪些串能被删空。下面只考虑长度为偶数的串。考虑这样一个（错误的）算法：从左往右依次加入串中的字符，然后能删则删。这个算法对于结尾为A的串一定能删空。对称地，开头为B的串也一定能被删空。现在只需要考虑开头为A结尾为B的串。如果它能被删空，则一定存......
  • AtCoder Regular Contest 112 F Die Siedler
    洛谷传送门AtCoder传送门感觉太人类智慧了。设\(A=(c_1,c_2,...,c_n)\)表示当前每种牌的数量，\(f(A)\)为状态\(A\)只进行换牌操作最终最少剩下几张牌。\(f(A)\)是可以贪心求出的，因为策略必然是能换则换。并且我们发现依次换\(2,3,...,n,1\)，最后\(c_2\simc_n\)都......
  • Linux shell regular expression All In One
    LinuxshellregularexpressionAllInOneLinuxshell正则表达式demos(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99