【vijos】1882石段のレンガ(中位数+特殊なテクニック)

3366 ワード
OS
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 << 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は石段でレンガを游んでいた.彼らはみな自分のレンガの山を持っている.1人当たりのレンガはN列からなり、Nは奇数である.Aliceのi列目のレンガはm[i]個ある.Bobのi列目のレンガはs[i]個ある.
彼らは城を建てたいと思っています.同じ城が2つあります.各城は真ん中の列から始まる:1)左側を見ると、数がどんどん増え、各列が右側の列よりちょうど1枚多くなっている.2)右側を見ると、数がどんどん増えて、各列が左側の列よりちょうど1枚多くなっている.
では、一番左側と一番右側の高さはもちろん同じですね.
毎回彼らはレンガを捨てて、ある列のレンガの数を減らすことができます.これは操作です.彼らはレンガをもう1枚探して、ある列のレンガの数を増やすことができます.これはまた操作です.でも1列からレンガを1枚取り除き、別の列に置くことはできない.捨てられたレンガは、二度と使われない.
最低、最低、何回の操作が必要ですか?
書式設定
入力フォーマット
入力データの第1行:奇数N、1<=N<=300000、AliceとBobがそれぞれ何列のレンガを持っているかを示す.2行目にはN個の整数、m[i],0<=m[i]<=1億億円がある.Aliceの列ごとのレンガの個数を表す.3行目にはN個の整数、s[i],0<=s[i]<=1億億円がある.Bobの各列のレンガの個数を表す.
出力フォーマット
出力は1行のみであり、最小の操作回数が要求する.
サンプル1
サンプル入力1 [コピー]
3

1 2 3

3 2 2

サンプル出力1 [コピー]
3

サンプル2
サンプル入力2 [コピー]
5

2 3 0 1 4

3 3 2 3 1

サンプル出力2 [コピー]
10

制限
40%のデータに対して:N<=1000は60%のデータに対して:N<=300000;0<=s[i],m[i]<=1000000は100%のデータに対して:N<=300000;0<=s[i],m[i]<=1,000,000,000,000
ヒント
サンプル1の解釈:Aliceはその第1列にレンガを2枚追加した.Bobは3列目にレンガを追加した.では、2人が建てた城の1列当たりのレンガの数は、3 2 3が同じで、要求を満たしている.
Pythonサーバ管理ツールの実装
hexo permalink設定テクニック