[ 오늘의 연습 ] 1. 622D

http://codeforces.com/problemset/problem/622/D

문제

$\displaystyle\sum_{i=1}^{n}{(n-i)\left|d_i+i-n\right|}$ 의 최소값이 되게하는 배열을 구하여라.

여기서, $d_i$는 배열 a에서 (i가 두 번째로 나타나는 위치) - (i가 첫 번쨰로 나타나는 위치)를 의미한다.

키포인트

곱해주는 값이 둘다 0보다 크거나 같은 양수이므로, 모든 항의 값을 0으로 만들 수 있는 방법에 대해 고민해본다.

1) i=n

0이다. 자명

2) i$\neq$n

뒤의 절댓값을 0으로 맞출 생각해보자. i<n이므로 i-n은 항상 음수이다. 따라서, $d_i$의 값을 n-i로 하면 0이 n-i+(i-n)을 하면 0이 되고, i-n<0이므로 n-i>0이다.

거리가 항상 0보다 커야한다는 것도 만족하므로 이를 기반으로 코드를 짜면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n; scanf("%d",&n);
    vector<int> ans(2*n+10,-1);
    for(int i=1;i<=n;i++)
    {
        if(i%2) ans[2*n-i/2]=i,ans[2*n-i/2+i-n]=i;
        else ans[i/2]=i,ans[i/2+n-i]=i;
    }
    for(int i=1;i<=2*n;i++) printf("%d ",ans[i]==-1 ? i : ans[i]);
    return 0;
}