はまやんはまやんはまやん

hamayanhamayan's blog

たぴの配置 [yukicoder 909]

https://yukicoder.me/problems/no/909

解説

https://yukicoder.me/submissions/391180

たぴ1から考えてみると、なるべく離したいので、たぴ0からXiの距離に置きたい。
あと、たぴN+1とも極力離したいので、Yiの距離に置きたい。
すると、Xi+Yiだけの距離ができる。
しかも、これ以上増やすと条件を満たさなくなるので、答えはXi+Yi以下になる。
すべての条件について考えると、すべてのたぴについて条件を満たす答えの中で最大のものは、Xi+Yiの最小値となる。
よって、それが答えansになる。

そこからの復元はたぴ0が座標0, たぴN+1が座標ansである。
たぴiは基本はXiの位置に置けばいいが、Xiがansを超えている場合はansに置けばいい。

int N, X[201010], Y[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i];
    rep(i, 0, N) cin >> Y[i];

    int ans = inf;
    rep(i, 0, N) chmin(ans, X[i] + Y[i]);
    printf("%d\n", ans);

    printf("0\n");
    rep(i, 0, N) printf("%d\n", min(X[i], ans));
    printf("%d\n", ans);

}