首页 > 代码库 > 【vijos】1882 石阶上的砖(中位数+特殊的技巧)
【vijos】1882 石阶上的砖(中位数+特殊的技巧)
https://vijos.org/p/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 << endlinline 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[复制]
31 2 33 2 2
样例输出1[复制]
3
样例2
样例输入2[复制]
52 3 0 1 43 3 2 3 1
样例输出2[复制]
10
限制
对于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 是相同的且满足要求.
【vijos】1882 石阶上的砖(中位数+特殊的技巧)