C. Warrior and Archer

C. Warrior and Archer

Math, Game


출처: Codeforces C. Warrior and Archer

Sol)
 game 문제 서로 최선을 다한다.
=> 그리디로 안풀린다. 모든 경우를 본다. 디피를 쓰든 어떻게든..
아처는 무조건 가운데를 없애고 워리어는 양 끝점을 없앤다.


[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<limits.h>
using namespace std;
int a[200000];
int ans = INT_MAX;
int main(){
    //freopen("input.txt", "r", stdin);
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    int m = n / 2;
    for (int i = 0; m + i < n; i++)
        ans = min(ans, a[m + i] - a[i]);
    printf("%d", ans);
    return 0;
}