시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB65637828462.009%

문제

수열 A1, A2 .. AN 이 주어진다.

B1 < B2 < ... < BN 을 만족하면서, |B1 - A1| + |B2 - A2| ... |BN - AN| 을 최소화하는 수열 B가 존재할 때, 당신은 그러한 값의 가능한 최솟값을 출력해야 한다.

수열 A와 B는 정수로만 이루어진 수열이고, 수열 B의 원소는 32비트 정수형 범위 안에 들어있어야 한다.

입력

첫 번째 줄에 N이 주어진다. (N ≤ 1,000,000) 두 번째 줄에 수열 A의 원소가 순서대로 주어진다. (0 ≤ Ai ≤ 2 × 109

출력

가능한 |B1 - A1| + |B2 - A2| ... |BN - AN| 값의 최소를 출력한다.

예제 입력 1

7
9 4 8 20 14 15 18

예제 출력 1

13

힌트

B = {6,7,8,13,14,15,18} 수열이 |B1 - A1| + |B2 - A2| ... |BN - AN| 값을 최소화한다. 최소화된 값은 13이다. 

W3sicHJvYmxlbV9pZCI6IjEzMzIzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQk9KIFx1YzIxOFx1YzVmNCAxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM1ZjQgQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+IC4uIEE8c3ViPk48XC9zdWI+IFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkI8c3ViPjE8XC9zdWI+ICZsdDsgQjxzdWI+MjxcL3N1Yj4gJmx0OyAuLi4gJmx0OyBCPHN1Yj5OPFwvc3ViPiBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjLCB8QjxzdWI+MTxcL3N1Yj4gLSBBPHN1Yj4xPFwvc3ViPnwgKyB8QjxzdWI+MjxcL3N1Yj4gLSBBPHN1Yj4yPFwvc3ViPnwgLi4uIHxCPHN1Yj5OPFwvc3ViPiAtIEE8c3ViPk48XC9zdWI+fCBcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNCBCXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWI1NGMsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhYzEyXHVjNzU4IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IEFcdWM2NDAgQlx1YjI5NCBcdWM4MTVcdWMyMThcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1YWNlMCwgXHVjMjE4XHVjNWY0IEJcdWM3NTggXHVjNmQwXHVjMThjXHViMjk0IDMyXHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOFx1ZDYxNSBcdWJjOTRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gJmxlOyAxLDAwMCwwMDApIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMiAmdGltZXM7Jm5ic3A7MTA8c3VwPjk8XC9zdXA+KSZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YjJhNVx1ZDU1YyB8QjxzdWI+MTxcL3N1Yj4gLSBBPHN1Yj4xPFwvc3ViPnwgKyB8QjxzdWI+MjxcL3N1Yj4gLSBBPHN1Yj4yPFwvc3ViPnwgLi4uIHxCPHN1Yj5OPFwvc3ViPiAtIEE8c3ViPk48XC9zdWI+fCBcdWFjMTJcdWM3NTggXHVjZDVjXHVjMThjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+QiA9IHs2LDcsOCwxMywxNCwxNSwxOH0gXHVjMjE4XHVjNWY0XHVjNzc0IHxCPHN1Yj4xPFwvc3ViPiAtIEE8c3ViPjE8XC9zdWI+fCArIHxCPHN1Yj4yPFwvc3ViPiAtIEE8c3ViPjI8XC9zdWI+fCAuLi4gfEI8c3ViPk48XC9zdWI+IC0gQTxzdWI+TjxcL3N1Yj58IFx1YWMxMlx1Yzc0NCBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NWNcdWIyZTQuIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1YjQxYyBcdWFjMTJcdWM3NDAgMTNcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMzMyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlcXVlbmNlIDEiLCJkZXNjcmlwdGlvbiI6IjxwPjx1PlNob3J0IGZvcm11bGF0aW9uLjxcL3U+IFRoZSBudW1iZXIgc2VxdWVuY2UgaXMgZ2l2ZW4uIFlvdXIgdGFzayBpcyB0byBjb25zdHJ1Y3QgdGhlIGluY3JlYXNpbmcgc2VxdWVuY2UgdGhhdCBhcHByb3hpbWF0ZXMgdGhlIGdpdmVuIG9uZSBpbiB0aGUgYmVzdCB3YXkuIFRoZSBiZXN0IGFwcHJveGltYXRpbmcgc2VxdWVuY2UgaXMgdGhlIHNlcXVlbmNlIHdpdGggdGhlIGxlYXN0IHRvdGFsIGRldmlhdGlvbiBmcm9tIHRoZSBnaXZlbiBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+PHU+TW9yZSBwcmVjaXNlbHkuPFwvdT4mbmJzcDtMZXQgdDxzdWI+MTxcL3N1Yj4sIHQ8c3ViPjI8XC9zdWI+LCAuLi4sIHQ8c3ViPk48XC9zdWI+IGlzIHRoZSBnaXZlbiBudW1iZXIgc2VxdWVuY2UuIFlvdXIgdGFzayBpcyB0byBjb25zdHJ1Y3QgdGhlIGluY3JlYXNpbmcgbnVtYmVyIHNlcXVlbmNlIHo8c3ViPjE8XC9zdWI+ICZsdDsgejxzdWI+MjxcL3N1Yj4gJmx0OyAuLi4gJmx0OyB6PHN1Yj5OPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+VGhlIHN1bSB8dDxzdWI+MTxcL3N1Yj4gLSB6PHN1Yj4xPFwvc3ViPnwgKyB8dDxzdWI+MjxcL3N1Yj4gLSB6PHN1Yj4yPFwvc3ViPnwgKyAuLi4gKyB8dDxzdWI+TjxcL3N1Yj4gLSB6PHN1Yj5OPFwvc3ViPnwgc2hvdWxkIGJlIGEgbWluaW1hbCBmZWFzaWJsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIGlzIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwMCkgaW4gdGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQuIEVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBnaXZlbiBzZXF1ZW5jZSBlbGVtZW50LiBUaGVyZSBpcyB0PHN1Yj5LPFwvc3ViPiZuYnNwO2luIHRoZSAoSysxKS10aCBsaW5lLiBBbnkgZWxlbWVudCBpcyBzYXRpc2Z5aW5nIHRvIHJlbGF0aW9uIDAgJmxlOyB0PHN1Yj5LPFwvc3ViPiZuYnNwOyZsZTsgMjAwMDAwMDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBtaW5pbWFsIHBvc3NpYmxlIHRvdGFsIGRldmlhdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2004 3-1번

  • 빠진 조건을 찾은 사람: jh05013
  • 문제를 번역한 사람: koosaga