【vijos】1882 石阶上的砖（中位数+特殊的技巧）

这种题很赞。。

以后记得这些绝对值最小的优先想中位数啊orz

首先我们将所有的高度都减掉他们的高度差，那么得到的应该是一串高低不平的数列，那么题目转化为，将这个改变后的数列变成一样高的最小费用。

那么显然是中位数啦。

好赞。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const ll getint() { ll r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=300005;

int n;

ll x, nx[N+N], ans;

int main() {

	read(n);

	for1(i, 1, n) nx[i]=getint()-abs(n/2-i+1);

	for1(i, 1, n) nx[n+i]=getint()-abs(n/2-i+1);

	sort(nx+1, nx+1+n+n);

	x=nx[n];

	for1(i, 1, n<<1) ans+=abs(nx[i]-x);

	printf("%lld", ans);

	return 0;

}

背景

微雨的山门下
石阶湿着——
只有独立的我
和缕缕的游云
这也是'同参密藏'么

描述

清晨, Alice与Bob在石阶上玩砖块.
他们每人都有属于自己的一堆砖块.
每人的砖块都由N列组成且N是奇数.
Alice的第i列砖块有m[i]个.
而Bob的第i列砖块有s[i]个.

他们想建造城堡, 两座一样的城堡.
每一座城堡都是从正中间一列开始:
1)若往左侧看去,数量逐次增加,每一列都比右侧的一列多出恰一块砖.
2)若往右侧看去,数量逐次增加,每一列都比左侧的一列多出恰一块砖.

那么,最左侧与最右侧的高度当然是一样的呵.

每一次.
他们可以扔掉一块砖头,以减少某一列的砖头数量.这算是一次操作.
他们可以再找一块砖头,以增加某一列的砖头数量.这又算是一次操作.
但是.
不能从一列去除一块砖头,再放置到别的列中.
被扔掉的砖头,永远也不能再被使用.

最少,最少,需要多少次操作?

格式

输入格式

输入数据第一行: 一个奇数N, 1<=N<=300,000, 表示Alice和Bob分别有多少列砖头.
第二行有N个整数, m[i], 0<=m[i]<=1,000,000,000,000. 表示Alice每一列的砖头个数.
第三行有N个整数, s[i], 0<=s[i]<=1,000,000,000,000. 表示Bob每一列的砖头个数.

输出格式

输出只有一行, 要求输出最少的操作次数.

样例1

样例输入1

样例输出1

样例2

样例输入2

样例输出2

限制

对于40%的数据:N<=1000
对于60%的数据:N<=300,000;0<=s[i],m[i]<=1,000,000
对于100%的数据:N<=300,000;0<=s[i],m[i]<=1,000,000,000,000

提示

样例1的解释: Alice对于其第一列新添两块砖. Bob对于其第三列新添一块砖.
那么,两人所建城堡每一列的砖头个数为: 3 2 3 是相同的且满足要求.